{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimize the Total Price of the Trips"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #graph #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #图 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumTotalPrice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小化旅行的价格总和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有一棵无向、无根的树，树中有 <code>n</code> 个节点，按从 <code>0</code> 到 <code>n - 1</code> 编号。给你一个整数 <code>n</code> 和一个长度为 <code>n - 1</code> 的二维整数数组 <code>edges</code> ，其中 <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> 表示树中节点 <code>a<sub>i</sub></code> 和 <code>b<sub>i</sub></code> 之间存在一条边。</p>\n",
    "\n",
    "<p>每个节点都关联一个价格。给你一个整数数组 <code>price</code> ，其中 <code>price[i]</code> 是第 <code>i</code> 个节点的价格。</p>\n",
    "\n",
    "<p>给定路径的 <strong>价格总和</strong> 是该路径上所有节点的价格之和。</p>\n",
    "\n",
    "<p>另给你一个二维整数数组 <code>trips</code> ，其中 <code>trips[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> 表示您从节点 <code>start<sub>i</sub></code> 开始第 <code>i</code> 次旅行，并通过任何你喜欢的路径前往节点 <code>end<sub>i</sub></code> 。</p>\n",
    "\n",
    "<p>在执行第一次旅行之前，你可以选择一些 <strong>非相邻节点</strong> 并将价格减半。</p>\n",
    "\n",
    "<p>返回执行所有旅行的最小价格总和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/03/16/diagram2.png\" style=\"width: 541px; height: 181px;\">\n",
    "<pre><strong>输入：</strong>n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]\n",
    "<strong>输出：</strong>23\n",
    "<strong>解释：\n",
    "</strong>上图表示将节点 2 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。\n",
    "第 1 次旅行，选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。\n",
    "第 2 次旅行，选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。\n",
    "第 3 次旅行，选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。\n",
    "所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明，23 是可以实现的最小答案。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/03/16/diagram3.png\" style=\"width: 456px; height: 111px;\">\n",
    "<pre><strong>输入：</strong>n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 并使其价格减半后的树。 \n",
    "第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。 \n",
    "所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 50</code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>edges</code> 表示一棵有效的树</li>\n",
    "\t<li><code>price.length == n</code></li>\n",
    "\t<li><code>price[i]</code> 是一个偶数</li>\n",
    "\t<li><code>1 &lt;= price[i] &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= trips.length &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>i</sub>, end<sub>i</sub>&nbsp;&lt;= n - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimize-the-total-price-of-the-trips](https://leetcode.cn/problems/minimize-the-total-price-of-the-trips/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimize-the-total-price-of-the-trips](https://leetcode.cn/problems/minimize-the-total-price-of-the-trips/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[0,1],[1,2],[1,3]]\\n[2,2,10,6]\\n[[0,3],[2,1],[2,3]]', '2\\n[[0,1]]\\n[2,2]\\n[[0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def saver(self,cur,cursave,neighbor,pre,cost):\n",
    "        p2=[]\n",
    "        cs1=cursave+cost[cur]/2\n",
    "        cs2=cursave\n",
    "        tmp=[]\n",
    "        for neigh in neighbor[cur]:\n",
    "            if neigh!=pre:\n",
    "                tmp.append(neigh)\n",
    "        p2=tmp\n",
    "        for next2 in p2:\n",
    "            cs2=max(cs2,self.saver(next2,cs2,neighbor,cur,cost))\n",
    "        if cost[cur]==0:\n",
    "            return cs2\n",
    "        for t in tmp:\n",
    "            for neigh in neighbor[t]:\n",
    "                if neigh!=cur:\n",
    "                    cs1=max(cs1,self.saver(neigh,cs1,neighbor,t,cost))\n",
    "        return max(cs1,cs2)\n",
    "\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        neighbor=dict()\n",
    "        for i in range(n):\n",
    "            neighbor[i]=[]\n",
    "        times=[]\n",
    "        for i in range(n):\n",
    "            times.append(0)\n",
    "        for e in edges:\n",
    "            neighbor[e[0]].append(e[1])\n",
    "            neighbor[e[1]].append(e[0])\n",
    "        allpath=[]\n",
    "        for t in trips:\n",
    "            start=t[0]\n",
    "            end=t[1]\n",
    "            queue = deque()\n",
    "            queue.append(start)\n",
    "            predecessors = {start: None}\n",
    "            while queue:\n",
    "                current = queue.popleft()\n",
    "                if current == end:\n",
    "                    path = []\n",
    "                    while current is not None:\n",
    "                        path.append(current)\n",
    "                        current = predecessors[current]\n",
    "                    finalpath=path[::-1]\n",
    "                    break\n",
    "                for neigh in neighbor[current]:\n",
    "                    if neigh not in predecessors:\n",
    "                        predecessors[neigh] = current\n",
    "                        queue.append(neigh)\n",
    "            for node in finalpath:\n",
    "                times[node]+=1\n",
    "        cost=[]\n",
    "        for i in range(n):\n",
    "            cost.append(times[i]*price[i])\n",
    "        for i,c in enumerate(cost):\n",
    "            if c!=0:\n",
    "                root=i\n",
    "        save=self.saver(i,0,neighbor,-1,cost)\n",
    "        return int(sum(cost)-save)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        cnt = [0] * n\n",
    "        for st, ed in trips:\n",
    "            def dfs(x, fa):\n",
    "                if x == ed:\n",
    "                    cnt[x] += 1\n",
    "                    return True\n",
    "                for y in g[x]:\n",
    "                    if y != fa and dfs(y, x):\n",
    "                        cnt[x] += 1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(st, -1)\n",
    "\n",
    "        def dfs(x, fa):\n",
    "            not_half = price[x] * cnt[x]\n",
    "            half = not_half // 2\n",
    "            for y in g[x]:\n",
    "                if y == fa: continue\n",
    "                nh, h = dfs(y, x)\n",
    "                not_half += min(nh, h)\n",
    "                half += nh\n",
    "            return not_half, half\n",
    "        return min(dfs(0, -1))\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        def dfs(root, ancestor):\n",
    "            if root == end:\n",
    "                return True\n",
    "            for edge in edges:\n",
    "                if root == edge[0] and edge[1] != ancestor:\n",
    "                    freq[edge[1]] += 1\n",
    "                    if dfs(edge[1], root): return True\n",
    "                    freq[edge[1]] -= 1\n",
    "                if root == edge[1] and edge[0] != ancestor:\n",
    "                    freq[edge[0]] += 1\n",
    "                    if dfs(edge[0], root): return True\n",
    "                    freq[edge[0]] -= 1\n",
    "        \n",
    "        def dfs_dp(root, ancestor):\n",
    "            cost_1 = price[root]//2*freq[root]\n",
    "            cost_0 = price[root]*freq[root]\n",
    "            for edge in edges:\n",
    "                if root == edge[0] and edge[1] != ancestor:\n",
    "                    cost_sub_1, cost_sub_0 = dfs_dp(edge[1], root)\n",
    "                    cost_1 += cost_sub_0\n",
    "                    cost_0 += min(cost_sub_0, cost_sub_1)\n",
    "                if root == edge[1] and edge[0] != ancestor:\n",
    "                    cost_sub_1, cost_sub_0 = dfs_dp(edge[0], root)\n",
    "                    cost_1 += cost_sub_0\n",
    "                    cost_0 += min(cost_sub_0, cost_sub_1)\n",
    "            return cost_1, cost_0\n",
    "        \n",
    "        freq = [0] * n\n",
    "        for trip in trips:\n",
    "            start, end = trip[0], trip[1]\n",
    "            freq[start] += 1\n",
    "            dfs(start, -1)\n",
    "        return min(dfs_dp(0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            x, y = edge\n",
    "            tree[x].append(y)\n",
    "            tree[y].append(x)\n",
    "        costs = [0 for _ in range(n)]\n",
    "        for start, end in trips:\n",
    "            def dfs(x, fa):\n",
    "                if x == end:\n",
    "                    costs[x] += price[x]\n",
    "                    return True\n",
    "                for nxt in tree[x]:\n",
    "                    if nxt != fa and dfs(nxt, x):\n",
    "                        costs[x] += price[x]\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(start, -1)\n",
    "        f = [[0 for _ in range(2)] for __ in range(n)]\n",
    "        def dp(x, fa):\n",
    "            f[x][0] = 0\n",
    "            f[x][1] = costs[x] // 2\n",
    "            for nxt in tree[x]:\n",
    "                if nxt == fa:\n",
    "                    continue\n",
    "                dp(nxt, x)\n",
    "                f[x][0] += max(f[nxt][0], f[nxt][1])\n",
    "                f[x][1] += f[nxt][0]\n",
    "        dp(0, -1)\n",
    "        return sum(costs) - max(f[0][0], f[0][1])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        if n == 1:\n",
    "            return len(trips) * price[0] // 2\n",
    "        adjList = [[] for _ in range(n)]\n",
    "        for x in edges:\n",
    "            adjList[x[0]].append(x[1])\n",
    "            adjList[x[1]].append(x[0])\n",
    "        weight = [0 for _ in range(n)]\n",
    "        for x in trips:\n",
    "            stack, already = [[x[0], 0]], {x[0]}\n",
    "            while stack[-1][0] != x[1]:\n",
    "                if stack[-1][1] == len(adjList[stack[-1][0]]):\n",
    "                    stack.pop()\n",
    "                elif adjList[stack[-1][0]][stack[-1][1]] not in already:\n",
    "                    stack.append([adjList[stack[-1][0]][stack[-1][1]], 0])\n",
    "                    already.add(stack[-1][0])\n",
    "                    stack[-2][1] += 1\n",
    "                else:\n",
    "                    stack[-1][1] += 1\n",
    "            for y in stack:\n",
    "                weight[y[0]] += 1\n",
    "        chosen, unchosen, degree, already, stack = [weight[i] * price[i] // 2 for i in range(n)], [0 for _ in range(n)], [len(adjList[i]) for i in range(n)], set(), [i for i in range(n) if len(adjList[i]) == 1]\n",
    "        while len(already) < n - 1:\n",
    "            pres = stack.pop()\n",
    "            already.add(pres)\n",
    "            for x in adjList[pres]:\n",
    "                if x not in already:\n",
    "                    target = x\n",
    "                else:\n",
    "                    chosen[pres] += unchosen[x]\n",
    "                    unchosen[pres] += max(chosen[x], unchosen[x])\n",
    "            degree[target] -= 1\n",
    "            if degree[target] == 1:\n",
    "                stack.append(target)\n",
    "        pres = stack.pop()\n",
    "        for x in adjList[pres]:\n",
    "            chosen[pres] += unchosen[x]\n",
    "            unchosen[pres] += max(chosen[x], unchosen[x])\n",
    "        return sum(price[i] * weight[i] for i in range(n)) - max(chosen[pres], unchosen[pres])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        # 由于价格最小，那么尽可能走一条最短的路 并记录所有走过的点 经过的次数\n",
    "        g = [[] for _ in range(n)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        cnt = [0]*n\n",
    "        for start, end in trips:\n",
    "            def travel(node, fa): # 到达end是否经过node\n",
    "                if node == end:\n",
    "                    cnt[node] += 1\n",
    "                    return True\n",
    "                for y in g[node]:\n",
    "                    if y != fa and travel(y, node): # 只有在确定能找到end时，才对路径上的节点次数增加\n",
    "                        cnt[node] += 1 # 这里是对node进行次数增加，因为确定经过node\n",
    "                        return True\n",
    "                return False\n",
    "            travel(start, -1)\n",
    "\n",
    "        def dfs(node, fa): # 返回选 不选 当前节点减半 在子树上的最小总和\n",
    "            pick, not_pick = price[node]//2*cnt[node], price[node]*cnt[node] \n",
    "            for y in g[node]:\n",
    "                if y != fa:\n",
    "                    son = dfs(y, node)\n",
    "                    pick += son[0]\n",
    "                    not_pick += min(son[1], son[0])\n",
    "            return not_pick, pick\n",
    "        return min(dfs(0, -1))\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        cnt = [0] * n\n",
    "        for start, end in trips:\n",
    "            def dfs(x: int, fa: int) -> bool:\n",
    "                if x == end:  # 到达终点（注意树只有唯一的一条简单路径）\n",
    "                    cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                    return True  # 找到终点\n",
    "                for y in g[x]:\n",
    "                    if y != fa and dfs(y, x):\n",
    "                        cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                        return True  # 找到终点\n",
    "                return False  # 未找到终点\n",
    "            dfs(start, -1)\n",
    "\n",
    "        def dfs(x, fa):\n",
    "            not_halve = price[x] * cnt[x]  # x 不变\n",
    "            halve = not_halve // 2  # x 减半\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    nh, h = dfs(y, x)  # 计算 y 不变/减半的最小价值总和\n",
    "                    not_halve += min(nh, h)  # x 不变，那么 y 可以不变，可以减半，取这两种情况的最小值\n",
    "                    halve += nh  # x 减半，那么 y 只能不变\n",
    "            return not_halve, halve\n",
    "        return min(dfs(0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "        cnt = [0] * n\n",
    "\n",
    "        def visit(x: int, p: int, target: int) -> bool:\n",
    "            if x == target:\n",
    "                cnt[x] += 1\n",
    "                return True\n",
    "            \n",
    "            for y in g[x]:\n",
    "                if y != p and visit(y, x, target):\n",
    "                    cnt[x] += 1\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        for s, e in trips:\n",
    "            visit(s, -1, e)\n",
    "        \n",
    "        def dfs(x: int, p: int) -> (int, int):\n",
    "            not_halve = price[x] * cnt[x]\n",
    "            halve = not_halve // 2\n",
    "\n",
    "            for y in g[x]:\n",
    "                if y != p:\n",
    "                    nh, h = dfs(y, x)\n",
    "                    not_halve += min(nh, h)\n",
    "                    halve += nh\n",
    "            return not_halve, halve\n",
    "        \n",
    "        return min(dfs(0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "\n",
    "        #先统计一下各个节点的贡献\n",
    "        cnt = [0] * n \n",
    "        for s, e in trips:\n",
    "            def dfs(u:int, fa:int)->bool:\n",
    "                if u == e:\n",
    "                    cnt[u] += 1\n",
    "                    return True\n",
    "                for v in g[u]:\n",
    "                    if v != fa and dfs(v, u):  #后面的路径能够到达终点\n",
    "                        cnt[u] += 1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(s, -1)\n",
    "\n",
    "\n",
    "        def dfs(u:int, fa:int)->(int, int): #不减半和减半\n",
    "            not_half = price[u] * cnt[u]\n",
    "            half = not_half // 2\n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    nn, yy = dfs(v, u)\n",
    "                    not_half += min(yy, nn)\n",
    "                    half += nn\n",
    "            return not_half, half\n",
    "        return min(dfs(0,-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        #简单路径上的代价就是每次旅行所需要的花费\n",
    "        #先预处理出所有节点需要经过的次数,树上求lca\n",
    "\n",
    "        '''\n",
    "        pa=[0]*n\n",
    "        x_len=[0]*n\n",
    "        def dfs(x:int,fa:int)->int:\n",
    "            for y in g[x]:\n",
    "                if y==fa:continue  \n",
    "                pa[y]=x\n",
    "                x_len[y]=x_len[x]+1\n",
    "                dfs(y,x)\n",
    "        dfs(0,-1)\n",
    "\n",
    "        cnt=[0]*n\n",
    "        def calc(x:int,y:int):\n",
    "            if x==y:\n",
    "                cnt[x]+=1\n",
    "                return\n",
    "            if x_len[x]>x_len[y]:\n",
    "                x,y=y,x\n",
    "            cnt[y]+=1\n",
    "            calc(x, pa[y])\n",
    "        \n",
    "        for s,e in trips:\n",
    "            calc(s, e)\n",
    "        '''\n",
    "\n",
    "        cnt=[0]*n\n",
    "        #dfs的自底向上写法没想到这么好用，必须好好掌握\n",
    "        def dfs(x:int,fa:int)->bool:\n",
    "            if x==e:\n",
    "                cnt[x]+=1\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y!=fa and dfs(y,x):\n",
    "                    cnt[x]+=1\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        for s,e in trips:\n",
    "            dfs(s, -1)\n",
    "\n",
    "        #类似选或不选的思想\n",
    "        def dfs2(x:int,fa:int)->(int,int):\n",
    "            s1,s2=cnt[x]*price[x]//2,cnt[x]*price[x]   #1代表减半了，2代表没减半\n",
    "            for y in g[x]:\n",
    "                if y==fa:continue  \n",
    "                f1,f2=dfs2(y,x)\n",
    "                s1+=f2\n",
    "                s2+=min(f1,f2)\n",
    "            return s1,s2\n",
    "        \n",
    "        return min(dfs2(0,-1))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        # 统计旅行路线经过的点\n",
    "        cnt = [0] * n\n",
    "        for start, end in trips:\n",
    "            def dfs(x, fa):\n",
    "                if x == end:\n",
    "                    cnt[x] += 1\n",
    "                    return True\n",
    "                for y in g[x]:\n",
    "                    if y != fa and dfs(y, x):\n",
    "                        cnt[x] += 1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(start, -1)\n",
    "        \n",
    "        # 类似打家劫舍\n",
    "        def dfs(x, fa):\n",
    "            not_half = price[x] * cnt[x]\n",
    "            half = not_half // 2\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    nh, h = dfs(y, x)\n",
    "                    not_half += min(nh, h)\n",
    "                    half += nh                    \n",
    "            return not_half, half\n",
    "        return min(dfs(0, -1))\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        cnt = [0] * n\n",
    "        for s,e in trips:\n",
    "            def dfs1(x = s,p = -1):\n",
    "                if x == e:\n",
    "                    cnt[x] += 1\n",
    "                    return True\n",
    "                for y in g[x]:\n",
    "                    if y != p and dfs1(y,x):\n",
    "                        cnt[x] += 1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs1()\n",
    "        def dp(x = 0,p = -1):\n",
    "            nodo = cnt[x] * price[x]\n",
    "            do = nodo // 2\n",
    "            for y in g[x]:\n",
    "                if y == p: continue\n",
    "                nd,d = dp(y,x)\n",
    "                nodo += min(nd,d)\n",
    "                do += nd\n",
    "            return nodo, do\n",
    "        return min(dp())\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        cnt = [0] * n\n",
    "\n",
    "        def dfs(x: int, fa: int) -> bool:\n",
    "            if x == end:  # 到达终点（注意树只有唯一的一条简单路径）\n",
    "                cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                return True  # 找到终点\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs(y, x):\n",
    "                    cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                    return True  # 找到终点\n",
    "            return False  # 未找到终点\n",
    "\n",
    "        for start, end in trips:\n",
    "            dfs(start, -1)\n",
    "\n",
    "        # 类似 337. 打家劫舍 III https://leetcode.cn/problems/house-robber-iii/\n",
    "        def dfs(x: int, fa: int) -> (int, int):\n",
    "            not_halve = price[x] * cnt[x]  # x 不变\n",
    "            halve = not_halve // 2  # x 减半\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    nh, h = dfs(y, x)  # 计算 y 不变/减半的最小价值总和\n",
    "                    not_halve += min(nh, h)  # x 不变，那么 y 可以不变，可以减半，取这两种情况的最小值\n",
    "                    halve += nh  # x 减半，那么 y 只能不变\n",
    "            return not_halve, halve\n",
    "        return min(dfs(0, -1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        # 由于价格最小，那么尽可能走一条最短的路 并记录所有走过的点 经过的次数\n",
    "        g = [[] for _ in range(n)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        cnt = [0]*n\n",
    "        for start, end in trips:\n",
    "            def travel(node, fa):\n",
    "                if node == end:\n",
    "                    cnt[node] += 1\n",
    "                    return True\n",
    "                for y in g[node]:\n",
    "                    if y != fa and travel(y, node): # 只有在确定能找到end时，才对路径上的节点次数增加\n",
    "                        cnt[node] += 1\n",
    "                        return True\n",
    "                return False\n",
    "            travel(start, -1)\n",
    "\n",
    "        def dfs(node, fa): # 返回选 不选 当前节点减半 在子树上的最小总和\n",
    "            pick, not_pick = price[node]//2*cnt[node], price[node]*cnt[node] \n",
    "            for y in g[node]:\n",
    "                if y != fa:\n",
    "                    son = dfs(y, node)\n",
    "                    pick += son[0]\n",
    "                    not_pick += min(son[1], son[0])\n",
    "            return not_pick, pick\n",
    "        return min(dfs(0, -1))\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "\n",
    "\n",
    "        cnt = [0] * n\n",
    "\n",
    "        def dfs(node, fa, end):\n",
    "            if node == end:\n",
    "                cnt[node] += 1\n",
    "                return True\n",
    "            for child in graph[node]:\n",
    "                if child != fa and dfs(child, node, end):\n",
    "                    cnt[node] += 1\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        for s, e in trips:\n",
    "            dfs(s, -1, e)\n",
    "\n",
    "\n",
    "\n",
    "        price = [p*cnt[i] for i, p in enumerate(price)]\n",
    "\n",
    "        def dfs2(cur, fa):\n",
    "            cur_price = price[cur]\n",
    "            zhe = cur_price // 2\n",
    "\n",
    "            for child in graph[cur]:\n",
    "                if child != fa:\n",
    "                    not_zhe, da_zhe = dfs2(child, cur)\n",
    "                    cur_price += min(not_zhe, da_zhe)\n",
    "                    zhe += not_zhe\n",
    "            return cur_price, zhe\n",
    "\n",
    "        return min(dfs2(0, -1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in  range(n)]\n",
    "        for s,e in edges:\n",
    "            g[s].append(e)\n",
    "            g[e].append(s)\n",
    "        cnt = [0]*n \n",
    "        for start,end in trips:\n",
    "            def dfs(x,fa):\n",
    "                if x==end:\n",
    "                    cnt[x]+=1\n",
    "                    return True\n",
    "                for c in g[x]:\n",
    "                    if c!=fa and dfs(c,x):\n",
    "                        cnt[x]+=1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(start,-1)\n",
    "        # print(cnt)\n",
    "        def dfs(x,fa):\n",
    "            s1,s2 = [],[]\n",
    "            for c in g[x]:\n",
    "                if c==fa:\n",
    "                    continue\n",
    "                get,no_get = dfs(c,x)# 打折、不打折\n",
    "                s1.append(get)\n",
    "                s2.append(no_get)\n",
    "            have= price[x]//2*cnt[x]+sum(s2)\n",
    "            no_have = price[x]*cnt[x]+sum([min(a,b) for a,b in zip(s1,s2)])\n",
    "            #print(x,have,no_have)\n",
    "            return have,no_have\n",
    "        return min(dfs(0,-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            x, y = edge\n",
    "            tree[x].append(y)\n",
    "            tree[y].append(x)\n",
    "        costs = [0 for _ in range(n)]\n",
    "        for start, end in trips:\n",
    "            def dfs(x, fa):\n",
    "                if x == end:\n",
    "                    costs[x] += price[x]\n",
    "                    return True\n",
    "                for nxt in tree[x]:\n",
    "                    if nxt != fa and dfs(nxt, x):\n",
    "                        costs[x] += price[x]\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(start, -1)\n",
    "        f = [[0 for _ in range(2)] for __ in range(n)]\n",
    "        def dp(x, fa):\n",
    "            for nxt in tree[x]:\n",
    "                if nxt == fa:\n",
    "                    continue\n",
    "                dp(nxt, x)\n",
    "            f[x][0] = 0\n",
    "            f[x][1] = costs[x] // 2\n",
    "            for nxt in tree[x]:\n",
    "                if nxt != fa:\n",
    "                    f[x][0] += max(f[nxt][0], f[nxt][1])\n",
    "                    f[x][1] += f[nxt][0]\n",
    "        dp(0, -1)\n",
    "        return sum(costs) - max(f[0][0], f[0][1])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 建树\n",
    "# 统计每个路径经过点的次数\n",
    "# 根据节点的减半计算整体开销\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        cnt = [0]*n\n",
    "        for start, end in trips:\n",
    "            def travel(node, fa):\n",
    "                if node==end:\n",
    "                    cnt[node] += 1\n",
    "                    return True\n",
    "                for y in g[node]:\n",
    "                    if y!=fa and travel(y, node):\n",
    "                        cnt[node] += 1\n",
    "                        return True\n",
    "                return False\n",
    "            travel(start, -1)\n",
    "        ans = 0\n",
    "        def dfs(node, fa): # 返回的是选不选\n",
    "            not_pick=price[node]*cnt[node]\n",
    "            pick=not_pick//2\n",
    "            for y in g[node]:\n",
    "                if y!=fa:\n",
    "                    y_not_pick, y_pick=dfs(y, node)\n",
    "                    not_pick += min(y_not_pick, y_pick)\n",
    "                    pick += y_not_pick\n",
    "            return not_pick, pick\n",
    "        return min(dfs(0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        next = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            next[edge[0]].append(edge[1])\n",
    "            next[edge[1]].append(edge[0])\n",
    "        \n",
    "        count = [0] * n\n",
    "        def dfs(node: int, parent: int, end: int) -> bool:\n",
    "            if node == end:\n",
    "                count[node] += 1\n",
    "                return True\n",
    "            for child in next[node]:\n",
    "                if child == parent:\n",
    "                    continue\n",
    "                if dfs(child, node, end):\n",
    "                    count[node] += 1\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        for [x, y] in trips:\n",
    "            dfs(x, -1, y)\n",
    "        \n",
    "        def dp(node: int, parent: int) -> List[int]:\n",
    "            res = [\n",
    "                price[node] * count[node], price[node] * count[node] // 2\n",
    "            ]\n",
    "            for child in next[node]:\n",
    "                if child == parent:\n",
    "                    continue\n",
    "                [x, y] = dp(child, node)\n",
    "                # node 没有减半，因此可以取子树的两种情况的最小值\n",
    "                # node 减半，只能取子树没有减半的情况\n",
    "                res[0], res[1] = res[0] + min(x, y), res[1] + x\n",
    "            return res\n",
    "\n",
    "        return min(dp(0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        #prices的大小比较小，可以先DFS把每个节点经过多少次算出来(所以dfs要从trip中的start开始，然后因为这是图，所以要考虑不能回头经过父亲，所以dfs中含有父亲节点的序号)，然后把这个问题化成只DFS一遍\n",
    "        #求权和的问题，打家劫舍是选或者不选，这里依然是，只不过选不选是减不减半\n",
    "        #先建树,防止经过父亲也可以用vis数组表示，vis过了就不了，对于图就是要用vis数组，比如Tarjan\n",
    "        g=[[] for i in range(n)]\n",
    "        cnt=[0]*n\n",
    "        #孩子节点表示法\n",
    "        for i in range(len(edges)):\n",
    "            g[edges[i][0]].append(edges[i][1])\n",
    "            g[edges[i][1]].append(edges[i][0])\n",
    "        for start,end in trips:\n",
    "            def dfs(x,fa) -> bool:\n",
    "                if x==end:\n",
    "                    cnt[x]+=1\n",
    "                    #找到了\n",
    "                    return True\n",
    "                #没有到终点，哪里要增加？能到终点的路径增加(只能有一条这样的路径，树决定的)\n",
    "                for y in g[x]:\n",
    "                    if y!=fa and dfs(y,x):\n",
    "                        \n",
    "                        #这里是cnt[x]，注意逻辑，是先加这个点，比如起点进去了，起点这个就要加\n",
    "\n",
    "                        cnt[x]+=1\n",
    "                        return True\n",
    "                #都没找到\n",
    "                return False\n",
    "            dfs(start,-1)   #start没有父亲节点\n",
    "        #把prices更新一下得到新prices，再做这个新问题\n",
    "        new_price=[price[i]*cnt[i] for i in range(len(price))]\n",
    "        #然后从任何一个点开始遍历，考虑dfs的分类讨论即可\n",
    "        def dfs(x,fa) -> (int,int):\n",
    "            #x减半或者不减半,先进行初始化(每次dfs开的变量都不同的，都是局部变量，不用担心)\n",
    "            choose=new_price[x]//2\n",
    "            not_choose=new_price[x]\n",
    "            for y in g[x]:\n",
    "                if y!=fa:\n",
    "                    half,not_half=dfs(y,x)\n",
    "                    choose+=not_half\n",
    "                    not_choose+=min(half,not_half)\n",
    "            return choose,not_choose\n",
    "        return min(dfs(0,-1))\n",
    "            \n",
    "            \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        cnt = [0] * n # 统计每个点的经过次数\n",
    "        for start, end in trips:\n",
    "            def dfs1(x: int, fa: int) -> bool:\n",
    "                if x == end:\n",
    "                    cnt[x] += 1\n",
    "                    return True\n",
    "                for y in g[x]:\n",
    "                    if y != fa and dfs1(y, x):\n",
    "                        cnt[x] += 1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs1(start, -1)\n",
    "        # 树形DP\n",
    "        def dfs2(x: int, fa: int) -> (int, int):\n",
    "            not_half = cnt[x] * price[x]\n",
    "            half = not_half // 2\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    hf, not_hf = dfs2(y, x)\n",
    "                    half += not_hf\n",
    "                    not_half += min(hf, not_hf)\n",
    "            return (half, not_half)\n",
    "        return min(dfs2(0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        cnt = [0] * n\n",
    "        for start, end in trips:\n",
    "            def dfs(x: int, fa: int) -> bool:\n",
    "                if x == end:  # 到达终点（注意树只有唯一的一条简单路径）\n",
    "                    cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                    return True  # 找到终点\n",
    "                for y in g[x]:\n",
    "                    if y != fa and dfs(y, x):\n",
    "                        cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                        return True  # 找到终点\n",
    "                return False  # 未找到终点\n",
    "            dfs(start, -1)\n",
    "\n",
    "        # 类似 337. 打家劫舍 III https://leetcode.cn/problems/house-robber-iii/\n",
    "        def dfs(x: int, fa: int) -> (int, int):\n",
    "            not_halve = price[x] * cnt[x]  # x 不变\n",
    "            halve = not_halve // 2  # x 减半\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    nh, h = dfs(y, x)  # 计算 y 不变/减半的最小价值总和\n",
    "                    not_halve += min(nh, h)  # x 不变，那么 y 可以不变，可以减半，取这两种情况的最小值\n",
    "                    halve += nh  # x 减半，那么 y 只能不变\n",
    "            return not_halve, halve\n",
    "        return min(dfs(0, -1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g=[[]for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        cnt=[0]*n\n",
    "        for start,end in trips:\n",
    "            def dfs(x,fa):\n",
    "                if x==end:\n",
    "                    cnt[x]+=1\n",
    "                    return True\n",
    "                for y in g[x]:\n",
    "                    if y!=fa and dfs(y,x):\n",
    "                        cnt[x]+=1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(start,-1)\n",
    "        def dfs(x,fa):\n",
    "            not_half=price[x]*cnt[x]\n",
    "            half=not_half/2\n",
    "            for y in g[x]:\n",
    "                if y!=fa:\n",
    "                    nh,h=dfs(y,x)\n",
    "                    not_half+=min(h,nh)\n",
    "                    half+=nh\n",
    "            return not_half,half\n",
    "        return int(min(dfs(0,-1)))\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        t=[0]*n\n",
    "        def dfs(x,end,fa):\n",
    "            if x==end:\n",
    "                return True\n",
    "\n",
    "            for nxt in g[x]:\n",
    "                if nxt!=fa:\n",
    "                    if dfs(nxt,end,x):\n",
    "                        t[nxt]+=1\n",
    "                        return True\n",
    "            return False\n",
    "        for start,end in trips:\n",
    "            t[start]+=1\n",
    "            dfs(start,end,-1)\n",
    "        print(t)\n",
    "        def dfs1(x,fa):\n",
    "            sum1=price[x]*t[x]\n",
    "            sum2=price[x]*t[x]//2\n",
    "            for nxt in g[x]:\n",
    "                if nxt!=fa:\n",
    "                    cur=dfs1(nxt,x)\n",
    "                    sum1+=min(cur)\n",
    "                    sum2+=cur[1]\n",
    "            return (sum2,sum1)\n",
    "        return min(dfs1(0,-1))\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        #指定了起点和终点，树肯定是只有唯一的一条路径到达的\n",
    "        es = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            es[u].append(v)\n",
    "            es[v].append(u)\n",
    "        def getRoot(start,des,fa):\n",
    "            if start == des:\n",
    "                return [start]\n",
    "            for to in es[start]:\n",
    "                if to == fa:\n",
    "                    continue\n",
    "                ret = getRoot(to,des,start)\n",
    "                if ret:\n",
    "                    ret.append(start)\n",
    "                    return ret\n",
    "        \n",
    "        cnt = [0]*n\n",
    "        for x,y in trips:\n",
    "            root = getRoot(x,y,-1)\n",
    "            for node in root:\n",
    "                cnt[node] += 1\n",
    "        \n",
    "        #树形dp 当前根节点减半/当前根节点不减半\n",
    "        dp = [[0]*2 for i in range(n)]\n",
    "        #dp[node][0/1]:选择或者不选\n",
    "        #dp[node][0] = sum(max(dp[child][0],dp[child][1])) + cnt[cur] * price[cur]\n",
    "        #dp[node][1] = sum(dp[child][0]) + cnt[cur] * price[cur]\n",
    "        def dfs(cur,fa):\n",
    "            dp[cur][1] = price[cur] // 2 * cnt[cur]\n",
    "            dp[cur][0] = price[cur] * cnt[cur]\n",
    "            for child in es[cur]:\n",
    "                if child == fa:\n",
    "                    continue\n",
    "                dfs(child,cur)\n",
    "                dp[cur][0] += min(dp[child][0],dp[child][1])\n",
    "                dp[cur][1] += dp[child][0]\n",
    "            return\n",
    "        dfs(0,-1)\n",
    "        return min(dp[0][0],dp[0][1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        # 1. 计算每个节点需要经过的次数\n",
    "        # 2， 树形dp，找出最小的cost\n",
    "\n",
    "        # 建树\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            tree[x].append(y)\n",
    "            tree[y].append(x)\n",
    "        print(tree)\n",
    "        # 1.找cnt\n",
    "        cnt = [0] * n\n",
    "        for start, end in trips:\n",
    "            # 找路径，找到终点x就返回true\n",
    "            def dfs(x: int, father: int) -> bool:\n",
    "                if x == end:\n",
    "                    cnt[x] += 1\n",
    "                    return True\n",
    "                for y in tree[x]:\n",
    "                    if y != father and dfs(y, x):\n",
    "                        cnt[x] += 1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(start, -1)\n",
    "        print(cnt)\n",
    "        \n",
    "        # 2.dp\n",
    "        # return (当前节点减半， 不减半)\n",
    "        def dfs(x: int, father:int) ->(int, int):\n",
    "            not_halve = price[x] * cnt[x]\n",
    "            halve = not_halve//2\n",
    "            for y in tree[x]:\n",
    "                if y != father:\n",
    "                    nh, h = dfs(y, x)\n",
    "                    not_halve += min(nh, h)\n",
    "                    halve += nh\n",
    "            return not_halve, halve\n",
    "        return min(dfs(0, -1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        cnt = Counter()\n",
    "        adj = defaultdict(list)\n",
    "\n",
    "        for u, v in edges:\n",
    "            adj[u].append(v)\n",
    "            adj[v].append(u)\n",
    "        \n",
    "        for st, ed in trips:\n",
    "            def dfs(x, fa):\n",
    "                if x == ed:\n",
    "                    cnt[x] += 1\n",
    "                    return True\n",
    "                for y in adj[x]:\n",
    "                    if y == fa:\n",
    "                        continue\n",
    "                    if dfs(y, x):\n",
    "                        cnt[x] += 1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(st, -1)\n",
    "        \n",
    "        def dfs(x, fa):\n",
    "            ret1 = price[x] * cnt[x]\n",
    "            ret2 = ret1 // 2\n",
    "\n",
    "            for y in adj[x]:\n",
    "                if y == fa:\n",
    "                    continue\n",
    "                r1, r2 = dfs(y, x)\n",
    "                ret1 += min(r1, r2)\n",
    "                ret2 += r1\n",
    "            return ret1, ret2\n",
    "        return min(dfs(0, -1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        cnt = [0] * n \n",
    "        for s, e in trips:\n",
    "            def dfs(node, par):\n",
    "                if node == e:\n",
    "                    cnt[node] += 1 \n",
    "                    return True \n",
    "                for nei in graph[node]:\n",
    "                    if nei == par:\n",
    "                        continue \n",
    "                    if dfs(nei, node):\n",
    "                        cnt[node] += 1 \n",
    "                        return True \n",
    "                return False \n",
    "            dfs(s, - 1)\n",
    "        def dfs(node, par):\n",
    "            nh, h = price[node] * cnt[node], price[node] * cnt[node] // 2 \n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                nxt = dfs(nei, node)\n",
    "                nh += min(nxt)\n",
    "                h += nxt[0]\n",
    "            return nh, h \n",
    "        return min(dfs(0, - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        cnt = [0] * n\n",
    "        for start, end in trips:\n",
    "            def dfs(x: int, fa: int) -> bool:\n",
    "                if x == end:  # 到达终点（注意树只有唯一的一条简单路径）\n",
    "                    cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                    return True  # 找到终点\n",
    "                for y in g[x]:\n",
    "                    if y != fa and dfs(y, x):\n",
    "                        cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                        return True  # 找到终点\n",
    "                return False  # 未找到终点\n",
    "            dfs(start, -1)\n",
    "\n",
    "        # 类似 337. 打家劫舍 III https://leetcode.cn/problems/house-robber-iii/\n",
    "        def dfs(x: int, fa: int) -> (int, int):\n",
    "            not_halve = price[x] * cnt[x]  # x 不变\n",
    "            halve = not_halve // 2  # x 减半\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    nh, h = dfs(y, x)  # 计算 y 不变/减半的最小价值总和\n",
    "                    not_halve += min(nh, h)  # x 不变，那么 y 可以不变，可以减半，取这两种情况的最小值\n",
    "                    halve += nh  # x 减半，那么 y 只能不变\n",
    "            return not_halve, halve\n",
    "        return min(dfs(0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        cnt = [0] * n\n",
    "        for start, end in trips:\n",
    "            def dfs(x: int, fa: int) -> bool:\n",
    "                if x == end:  #! 到达终点（注意树只有唯一的一条简单路径）\n",
    "                    cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                    return True  # 找到终点\n",
    "                for y in g[x]:\n",
    "                    if y != fa and dfs(y, x):\n",
    "                        cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                        return True  # 找到终点\n",
    "                return False  # 未找到终点\n",
    "            dfs(start, -1)\n",
    "\n",
    "        # 类似 337. 打家劫舍 III https://leetcode.cn/problems/house-robber-iii/\n",
    "        def dfs(x: int, fa: int) -> (int, int):\n",
    "            not_halve = price[x] * cnt[x]  # x 不变\n",
    "            halve = not_halve // 2  # x 减半\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    nh, h = dfs(y, x)  # 计算 y 不变/减半的最小价值总和\n",
    "                    not_halve += min(nh, h)  # x 不变，那么 y 可以不变，可以减半，取这两种情况的最小值\n",
    "                    halve += nh  # x 减半，那么 y 只能不变\n",
    "            return not_halve, halve\n",
    "        return min(dfs(0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        cnt = [0] * n\n",
    "        for start,end in trips:\n",
    "            def dfs(x,fa):\n",
    "                if x == end:\n",
    "                    cnt[x] += 1\n",
    "                    return True\n",
    "                for y in g[x]:\n",
    "                    if y != fa and dfs(y,x):\n",
    "                        cnt[x] += 1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(start,-1)\n",
    "        \n",
    "        def dfs(x,fa):\n",
    "            not_halve = cnt[x] * price[x]\n",
    "            halve = not_halve // 2\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    nh,h = dfs(y,x)\n",
    "                    not_halve += min(nh,h)\n",
    "                    halve += nh\n",
    "            return not_halve,halve\n",
    "        return min(dfs(0,-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        cnt = [0] * n\n",
    "        for start, end in trips:\n",
    "            def dfs(x: int, fa: int) -> bool:\n",
    "                if x == end:  # 到达终点（注意树只有唯一的一条简单路径）\n",
    "                    cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                    return True  # 找到终点\n",
    "                for y in g[x]:\n",
    "                    if y != fa and dfs(y, x):\n",
    "                        cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                        return True  # 找到终点\n",
    "                return False  # 未找到终点\n",
    "            dfs(start, -1)\n",
    "\n",
    "        def dfs(x: int, fa: int) -> (int, int):\n",
    "            not_halve = price[x] * cnt[x]  # x 不变\n",
    "            halve = not_halve // 2  # x 减半\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    nh, h = dfs(y, x)  # 计算 y 不变/减半的最小价值总和\n",
    "                    not_halve += min(nh, h)  # x 不变，那么 y 可以不变，可以减半，取这两种情况的最小值\n",
    "                    halve += nh  # x 减半，那么 y 只能不变\n",
    "            return not_halve, halve\n",
    "        return min(dfs(0, -1))\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        cnt = [0] * n\n",
    "        for edge in edges:\n",
    "            g[edge[0]].append(edge[1])\n",
    "            g[edge[1]].append(edge[0])\n",
    "        for start, end in trips:\n",
    "            def dfs(x, fa):\n",
    "                if x == end:\n",
    "                    cnt[x] += 1\n",
    "                    return True\n",
    "                for y in g[x]:\n",
    "                    if y != fa:\n",
    "                        if dfs(y, x):\n",
    "                            cnt[x] += 1\n",
    "                            return True\n",
    "                return False\n",
    "            dfs(start, -1)\n",
    "        def dfs(x, fa):\n",
    "            not_halve = price[x] * cnt[x]\n",
    "            halve = not_halve // 2\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    nh, h = dfs(y, x)\n",
    "                    not_halve += min(nh, h)\n",
    "                    halve += nh\n",
    "            return not_halve, halve\n",
    "        return min(dfs(0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "        cnt = [0] * n\n",
    "\n",
    "        def visit(x: int, p: int, target: int) -> bool:\n",
    "            if x == target:\n",
    "                cnt[x] += 1\n",
    "                return True\n",
    "            \n",
    "            for y in g[x]:\n",
    "                if y != p and visit(y, x, target):\n",
    "                    cnt[x] += 1\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        for s, e in trips:\n",
    "            visit(s, -1, e)\n",
    "        \n",
    "        def dfs(x: int, p: int) -> (int, int):\n",
    "            not_halve = price[x] * cnt[x]\n",
    "            halve = not_halve // 2\n",
    "\n",
    "            for y in g[x]:\n",
    "                if y != p:\n",
    "                    nh, h = dfs(y, x)\n",
    "                    not_halve += min(nh, h)\n",
    "                    halve += nh\n",
    "            return not_halve, halve\n",
    "        \n",
    "        return min(dfs(0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "            \n",
    "        cnt = [0] * n\n",
    "        for start, end in trips:\n",
    "            # 传入当前节点和他的父节点\n",
    "            def dfs(x: int, fa: int) -> bool:\n",
    "                if x == end:\n",
    "                    cnt[x] += 1\n",
    "                    return True\n",
    "                for y in g[x]:\n",
    "                    if y != fa and dfs(y, x):\n",
    "                        cnt[x] += 1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(start, -1)\n",
    "        \n",
    "        ## shuxing DP\n",
    "        def dp(x: int, fa: int) -> (int, int):\n",
    "            not_half = price[x] * cnt[x]\n",
    "            half = not_half // 2\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    nh, h = dp(y, x)\n",
    "                    not_half += min(nh, h)\n",
    "                    half += nh\n",
    "            return not_half, half\n",
    "        return min(dp(0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        cnt = [0] * n\n",
    "        for start, end in trips:\n",
    "            def dfs(x: int, fa: int) -> bool:\n",
    "                if x == end:  # 到达终点（注意树只有唯一的一条简单路径）\n",
    "                    cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                    return True  # 找到终点\n",
    "                for y in g[x]:\n",
    "                    if y != fa and dfs(y, x):\n",
    "                        cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                        return True  # 找到终点\n",
    "                return False  # 未找到终点\n",
    "            dfs(start, -1)\n",
    "\n",
    "        # 类似 337. 打家劫舍 III https://leetcode.cn/problems/house-robber-iii/\n",
    "        def dfs(x: int, fa: int) -> (int, int):\n",
    "            not_halve = price[x] * cnt[x]  # x 不变\n",
    "            halve = not_halve // 2  # x 减半\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    nh, h = dfs(y, x)  # 计算 y 不变/减半的最小价值总和\n",
    "                    not_halve += min(nh, h)  # x 不变，那么 y 可以不变，可以减半，取这两种情况的最小值\n",
    "                    halve += nh  # x 减半，那么 y 只能不变\n",
    "            return not_halve, halve\n",
    "        return min(dfs(0, -1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        next = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            next[edge[0]].append(edge[1])\n",
    "            next[edge[1]].append(edge[0])\n",
    "        \n",
    "        count = [0] * n\n",
    "        def dfs(node: int, parent: int, end: int) -> bool:\n",
    "            if node == end:\n",
    "                count[node] += 1\n",
    "                return True\n",
    "            for child in next[node]:\n",
    "                if child == parent:\n",
    "                    continue\n",
    "                if dfs(child, node, end):\n",
    "                    count[node] += 1\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        for [x, y] in trips:\n",
    "            dfs(x, -1, y)\n",
    "        \n",
    "        def dp(node: int, parent: int) -> List[int]:\n",
    "            res = [\n",
    "                price[node] * count[node], price[node] * count[node] // 2\n",
    "            ]\n",
    "            for child in next[node]:\n",
    "                if child == parent:\n",
    "                    continue\n",
    "                [x, y] = dp(child, node)\n",
    "                res[0], res[1] = res[0] + min(x, y), res[1] + x\n",
    "            return res\n",
    "\n",
    "        return min(dp(0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "\n",
    "        g=defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        def get(u,fa,e):\n",
    "            if u==e:return True\n",
    "            for v in g[u]:\n",
    "                if v==fa:continue\n",
    "                if get(v,u,e):\n",
    "                    cnt[v]+=1\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        \n",
    "        cnt=Counter()\n",
    "        for s,e in trips:\n",
    "            cnt[s]+=1\n",
    "            get(s,-1,e)\n",
    "\n",
    "        def dfs2(u,fa):\n",
    "            choose=cnt[u]*price[u]//2\n",
    "            nochoose=cnt[u]*price[u]\n",
    "\n",
    "            for v in g[u]:\n",
    "                if v==fa:continue\n",
    "                yes,no=dfs2(v,u)\n",
    "                choose+=no\n",
    "                nochoose+=min(yes,no)\n",
    "            return choose,nochoose\n",
    "        \n",
    "        a,b=dfs2(0,-1)\n",
    "        return min(a,b)\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "        \n",
    "        cnt = [0] *n\n",
    "\n",
    "        for start,end in trips:\n",
    "            def dfs(x,fa)->bool:\n",
    "                if x ==end:\n",
    "                    cnt[x]+=1\n",
    "                    return True\n",
    "                for y in g[x]:\n",
    "                    if y!=fa and dfs(y,x):\n",
    "                        cnt[x]+=1\n",
    "                        return True\n",
    "                return  False\n",
    "            dfs(start,-1)\n",
    "\n",
    "        def dfs(x,fa)->(int,int):\n",
    "            not_halve = price[x]*cnt[x]\n",
    "            havlve = not_halve //2\n",
    "            for y in g[x]:\n",
    "                if y!=fa:\n",
    "                    nh,h = dfs(y,x)\n",
    "                    not_halve += min(nh,h)\n",
    "                    havlve +=nh\n",
    "            return not_halve,havlve\n",
    "        \n",
    "        return min(dfs(0,-1))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: [[int]], price: [int], trips: [[int]]) -> int:\n",
    "\n",
    "        g = [[] for _ in range(n)]  # g[x] 表示 x 的所有邻居\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        dp=[0 for i in range(n)]\n",
    "        steps=[0 for i in range(n)]\n",
    "\n",
    "        target=0\n",
    "        def dfs(cur:int, fa:int, step:int):\n",
    "            nonlocal target\n",
    "            if cur==target:\n",
    "#                print(steps,step)\n",
    "                for i in range(step):\n",
    "                    dp[steps[i]]+=1\n",
    "                return\n",
    "\n",
    "            for x in g[cur]:\n",
    "                if x==fa: continue\n",
    "                steps[step]=x\n",
    "                dfs(x,cur,step+1)\n",
    "                steps[step]=0\n",
    "\n",
    "        for i in range(len(trips)):\n",
    "            target=trips[i][1]\n",
    "            steps[0]=trips[i][0]\n",
    "            dfs(steps[0],-1,1)\n",
    "\n",
    "        print(dp)\n",
    "        #dp表示在旅程中，总共被经过几次，代表了这节点的权重\n",
    "\n",
    "        ans=sys.maxsize     #ans为全局最优解\n",
    "        def getintree(cur:int, fa:int):     #统计到当前节点，时候的子树的最优质数据\n",
    "            nonlocal ans\n",
    "\n",
    "            lastson=[price[cur]*dp[cur], price[cur]*dp[cur]//2]   #计算自己节点时候的最小值\n",
    "\n",
    "            #lastson=[sys.maxsize,sys.maxsize]\n",
    "            for son in g[cur]:  # 遍历 x 的邻居 y\n",
    "                if son != fa:  # 避免访问父节点\n",
    "                    tmpson=getintree(son, cur)  # tmpson[0,1] 0表示当前节点没有减半时候的子树最小值； 1表示减少时候的最小值\n",
    "\n",
    "                    # cur没有减半的时候， 子节点任何情况都可以\n",
    "                    lastson[0]+=min(tmpson[0],tmpson[1])\n",
    "                    lastson[1]+=tmpson[0]\n",
    "            return lastson\n",
    "\n",
    "        tmp=getintree(0, -1)  # 以0为根，没有父节点\n",
    "        return min(tmp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        weights = [0] * n\n",
    "\n",
    "        def calc_weights(p: int, s: int, d: int) -> bool:\n",
    "            if s == d:\n",
    "                weights[d] += 1\n",
    "                return True\n",
    "            for v in g[s]:\n",
    "                if v == p:\n",
    "                    continue\n",
    "                if calc_weights(s, v, d):\n",
    "                    weights[s] += 1\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        for s, d in trips:\n",
    "            calc_weights(-1, s, d)\n",
    "\n",
    "        def dfs(u: int, v: int) -> tuple[int, int]:\n",
    "            sub = [dfs(v, w) for w in g[v] if w != u]\n",
    "            return (\n",
    "                price[v] // 2 * weights[v] + sum(x[1] for x in sub),\n",
    "                price[v] * weights[v] + sum(min(x) for x in sub),\n",
    "            )\n",
    "\n",
    "        return min(dfs(-1, 0))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        cnt = [0] * n \n",
    "        for s, e in trips:\n",
    "            def find(node, par):\n",
    "                if node == e:\n",
    "                    cnt[node] += 1 \n",
    "                    return True \n",
    "                for nei in graph[node]:\n",
    "                    if nei == par:\n",
    "                        continue \n",
    "                    if find(nei, node):\n",
    "                        cnt[node] += 1 \n",
    "                        return True\n",
    "                return False \n",
    "            find(s, - 1)\n",
    "        \n",
    "        def dfs(node, par):\n",
    "            h, nh = price[node] * cnt[node] // 2, price[node] * cnt[node]\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                nxt = dfs(nei, node)\n",
    "                h += nxt[1]\n",
    "                nh += min(nxt[0], nxt[1])\n",
    "            return h, nh \n",
    "        \n",
    "        return min(dfs(0, - 1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        neb = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            neb[u].append(v)\n",
    "            neb[v].append(u)\n",
    "        \n",
    "        def dfs(u, fa, target):\n",
    "            path.append(u)\n",
    "            if u == target:\n",
    "                for p in path:\n",
    "                    cnt[p] += 1\n",
    "            else:\n",
    "                for v in neb[u]:\n",
    "                    if v != fa:\n",
    "                        dfs(v, u, target)\n",
    "            path.pop()\n",
    "        \n",
    "        cnt = [0] * n\n",
    "        path = []\n",
    "        for u, v in trips:\n",
    "            dfs(u, -1, v)\n",
    "        print(cnt)\n",
    "\n",
    "        def dp(u, fa):\n",
    "            nc, cc = cnt[u]*price[u], cnt[u]*price[u]//2\n",
    "            child_nc, child_cc = inf, inf\n",
    "            for v in neb[u]:\n",
    "                if v != fa:\n",
    "                    nl, cl = dp(v, u)\n",
    "                    nc += min(nl, cl)\n",
    "                    cc += nl\n",
    "            return nc, cc\n",
    "                    \n",
    "            \n",
    "        return min(dp(0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        cnt = [0] * n\n",
    "        for start,end in trips:\n",
    "            def dfs(x,fa):\n",
    "                if x == end:\n",
    "                    cnt[x] += 1\n",
    "                    return True\n",
    "                for y in g[x]:\n",
    "                    if y != fa and dfs(y,x):\n",
    "                        cnt[x] += 1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(start,-1)\n",
    "        \n",
    "        def dfs(x,fa):\n",
    "            not_halve = cnt[x] * price[x]\n",
    "            halve = not_halve // 2\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    nh,h = dfs(y,x)\n",
    "                    not_halve += min(nh,h)\n",
    "                    halve += nh\n",
    "            return not_halve,halve\n",
    "        return min(dfs(0,-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        my_dict1=collections.defaultdict(list)#每个节点的子节点\n",
    "        for ai,bi in edges:\n",
    "            my_dict1[ai].append(bi)\n",
    "            my_dict1[bi].append(ai)\n",
    "\n",
    "        my_dict2=collections.defaultdict(int)#各个节点经过的次数\n",
    "\n",
    "        def myfun1(starti,endi,last):\n",
    "            if starti==endi:\n",
    "                my_dict2[starti]+=1\n",
    "                return 1\n",
    "            for i in my_dict1[starti]:\n",
    "                if i==last:\n",
    "                    continue\n",
    "                else:\n",
    "                    flag=myfun1(i,endi,starti)\n",
    "                    if flag:\n",
    "                        my_dict2[starti]+=1\n",
    "                        return 1\n",
    "            return 0\n",
    "\n",
    "        for starti,endi in trips:\n",
    "            myfun1(starti,endi,-1)\n",
    "\n",
    "\n",
    "        my_list2=[[0,0] for i in range(n)]\n",
    "\n",
    "        def myfun2(nnode,last):\n",
    "            temp0=price[nnode]*my_dict2[nnode]\n",
    "            temp1=price[nnode]*my_dict2[nnode]//2\n",
    "            for i in my_dict1[nnode]:\n",
    "                if i==last:\n",
    "                    continue\n",
    "                else:\n",
    "                    a,b=myfun2(i,nnode)\n",
    "                    temp0=temp0+min(a,b)\n",
    "                    temp1=temp1+a\n",
    "            return (temp0,temp1)\n",
    "\n",
    "        a,b=myfun2(0,-1)\n",
    "\n",
    "        return min(a,b)\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        # my_dict3=collections.defaultdict(int)#每个节点的入数\n",
    "        # my_list=[]\n",
    "        # my_list2=[[0,0] for i in range(n)]\n",
    "        # search_flag=[0]*n\n",
    "\n",
    "        # for key in my_dict1.keys():\n",
    "        #     temp_num=len(my_dict1[key])\n",
    "        #     if temp_num==1:\n",
    "        #         my_list.append(key)\n",
    "        #         my_list2[key][0]=my_dict2[key]*price[key]\n",
    "        #         my_list2[key][1]=my_dict2[key]*price[key]//2\n",
    "        #         search_flag[key]=1\n",
    "        #     my_dict3[key]=temp_num\n",
    "\n",
    "        # while my_list:\n",
    "        #     now_node=my_list.pop()\n",
    "        #     search_flag[now_node]==1\n",
    "        #     for j in my_dict1[now_node]:\n",
    "        #         if search_flag[j]==0:\n",
    "        #             my_list2[j][0]+=min(my_list2[now_node])\n",
    "        #             my_list2[j][1]+=my_list2[now_node][0]\n",
    "        #             my_dict3[j]-=1\n",
    "\n",
    "        #             if j in my_dict3 and my_dict3[j]==1:\n",
    "        #                 my_list.append(j)\n",
    "        #                 del my_dict3[j]\n",
    "\n",
    "        # return min(my_list2[now_node])\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        count = [0] * n\n",
    "        def node_count(u, f, dst):\n",
    "            if u == dst:\n",
    "                count[u] += 1\n",
    "                return True\n",
    "            \n",
    "            for v in graph[u]:\n",
    "                if v == f:\n",
    "                    continue\n",
    "                \n",
    "                found = node_count(v, u, dst)\n",
    "                if found:\n",
    "                    count[u] += 1\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        for start, end in trips:\n",
    "            node_count(start, -1, end)\n",
    "        \n",
    "        def helper(u, f):\n",
    "            a = price[u] * count[u]\n",
    "            b = a // 2\n",
    "            for v in graph[u]:\n",
    "                if v == f:\n",
    "                    continue\n",
    "                \n",
    "                _a, _b = helper(v, u)\n",
    "                a = min(a + _a, a + _b)\n",
    "                b = b + _a\n",
    "            return a, b\n",
    "        \n",
    "        return min(helper(0, -1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        weight = [0] * n  # 记录所有查询路径经过每个节点的次数\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "        for start, end in trips:\n",
    "            def dfs(x, fa):\n",
    "                if x == end:  # 到达终点\n",
    "                    weight[x] += 1\n",
    "                    return True\n",
    "                for y in g[x]:\n",
    "                    if y != fa and dfs(y, x):\n",
    "                        weight[x] += 1\n",
    "                        return True\n",
    "                return False\n",
    "\n",
    "            dfs(start, -1)\n",
    "\n",
    "        # print(weight)\n",
    "\n",
    "        for i in range(n):\n",
    "            price[i] = weight[i] * price[i] \n",
    "        g[0].append(-1)\n",
    "        print(price)\n",
    "        def getMin(x, fa):\n",
    "            if len(g[x]) == 1:\n",
    "                return price[x], 0\n",
    "            sel, nosel = 0, 0\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    selChild, noselChild = getMin(y, x)\n",
    "                    sel += max(noselChild, selChild)\n",
    "                    nosel += noselChild\n",
    "            return nosel + price[x], sel\n",
    "        a,b =getMin(0,-1)\n",
    "        # print(a,b)\n",
    "        sums = sum(price)\n",
    "        return sums-max(a,b)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        cnt = [0] * n\n",
    "        for start, end in trips:\n",
    "            def dfs(x: int, fa: int) -> bool:\n",
    "                if x == end:  # 到达终点（注意树只有唯一的一条简单路径）\n",
    "                    cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                    return True  # 找到终点\n",
    "                for y in g[x]:\n",
    "                    if y != fa and dfs(y, x):\n",
    "                        cnt[x] += 1  # 统计从 start 到 end 的路径上的点经过了多少次\n",
    "                        return True  # 找到终点\n",
    "                return False  # 未找到终点\n",
    "            dfs(start, -1)\n",
    "\n",
    "        # 类似 337. 打家劫舍 III https://leetcode.cn/problems/house-robber-iii/\n",
    "        def dfs(x: int, fa: int) -> (int, int):\n",
    "            not_halve = price[x] * cnt[x]  # x 不变\n",
    "            halve = not_halve // 2  # x 减半\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    nh, h = dfs(y, x)  # 计算 y 不变/减半的最小价值总和\n",
    "                    not_halve += min(nh, h)  # x 不变，那么 y 可以不变，可以减半，取这两种情况的最小值\n",
    "                    halve += nh  # x 减半，那么 y 只能不变\n",
    "            return not_halve, halve\n",
    "        return min(dfs(0, -1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        cnt = [0] * n\n",
    "        for start, end in trips:\n",
    "            def dfs(x: int, fa: int) -> bool:\n",
    "                if x == end:\n",
    "                    cnt[x] += 1\n",
    "                    return True\n",
    "                for y in g[x]:\n",
    "                    if y != fa and dfs(y, x):\n",
    "                        cnt[x] += 1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(start, -1)\n",
    "        \n",
    "        def dfs(x: int, fa: int) -> (int, int):\n",
    "            not_have = price[x] * cnt[x]\n",
    "            halve = not_have // 2\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    nh, h = dfs(y ,x)\n",
    "                    not_have += min(nh, h)\n",
    "                    halve += nh\n",
    "            return not_have, halve\n",
    "        \n",
    "        return min(dfs(0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "多次旅行使得难以决策到底选择哪些 非相邻 节点减半\n",
    "从路径下手\n",
    "由于是一颗树，从一个节点到另一个节点的路径肯定是固定好的。\n",
    "已知每个节点会被经过多少次\n",
    "\n",
    "那么一个节点选 或者不选，对答案的影响就显而易见了\n",
    "注意，由于输入不是一颗树，最好用dfs形式\n",
    "'''\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        cnt=[0]*n\n",
    "        for start,end in trips:\n",
    "            def dfs(x:int,fa:int)->bool:\n",
    "                if x==end:\n",
    "                    cnt[x]+=1\n",
    "                    return True\n",
    "                for y in g[x]:\n",
    "                    if y!=fa and dfs(y,x):\n",
    "                        cnt[x]+=1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(start,-1)\n",
    "\n",
    "        def dfs(x:int,fa:int)->(int,int):\n",
    "            non_half=price[x]*cnt[x]\n",
    "            half=non_half//2\n",
    "            for y in g[x]:\n",
    "                if y!=fa:\n",
    "                    nh,h=dfs(y,x)\n",
    "                    non_half+=min(nh,h)\n",
    "                    half+=nh\n",
    "            return non_half,half\n",
    "        return min(dfs(0,-1))\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    树形DP\n",
    "    题目有几个前提得先理解了：1.不允许走回头路；2.树意味着从点A出发到点B只能存在一条路\n",
    "    满足这两个前提下，我们可以先遍历trips，将所有旅行路径中经过点的次数统计出来，我们再按照树形DP的递归模版，\n",
    "    从任意点遍历整颗树的所有节点，计算节点本身在减半和不减半两种情况下，总trips途径所有节点以及次数的总和\n",
    "    '''\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        '''\n",
    "        计算trips中所有能经过节点的次数\n",
    "        '''\n",
    "        count = [0] * n\n",
    "        def node_count(u, f, dst):\n",
    "            if u == dst:\n",
    "                count[u] += 1\n",
    "                return True\n",
    "            \n",
    "            for v in graph[u]:\n",
    "                if v == f:\n",
    "                    continue\n",
    "                \n",
    "                found = node_count(v, u, dst)\n",
    "                if found:\n",
    "                    count[u] += 1\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        for start, end in trips:\n",
    "            node_count(start, -1, end)\n",
    "        \n",
    "        '''\n",
    "        递归计算所有节点结合trips中经过次数下的总价格\n",
    "        '''\n",
    "        def helper(u, f):\n",
    "            '''\n",
    "            当前节点分为减半和没有减半两种情况讨论\n",
    "            '''\n",
    "            a = price[u] * count[u]\n",
    "            b = a // 2\n",
    "            for v in graph[u]:\n",
    "                if v == f:\n",
    "                    continue\n",
    "                ''' \n",
    "                递归出以v为根节点没有遍历过节点的 砍半（v节点是否砍半）和 没有砍半 子树的总价格 \n",
    "                ''' \n",
    "                _a, _b = helper(v, u)\n",
    "                '''\n",
    "                当前节点没有砍半，可以选择相邻节点砍半，也可以选择相邻节点不砍半\n",
    "                当前节点砍半了，相邻节点只能不砍半\n",
    "                '''\n",
    "                a = min(a + _a, a + _b)\n",
    "                b = b + _a\n",
    "            return a, b\n",
    "        \n",
    "        return min(helper(0, -1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = collections.defaultdict(list)\n",
    "        for s,e in edges:\n",
    "            g[s].append(e)\n",
    "            g[e].append(s)\n",
    "\n",
    "        def dfs(s,e, vis):\n",
    "            if s == e: return True\n",
    "            for ne in g[s]:\n",
    "                if ne not in vis:\n",
    "                    vis.add(ne)\n",
    "                    d[ne] += price[ne]\n",
    "                    if dfs(ne, e, vis): return True\n",
    "                    vis.remove(ne)\n",
    "                    d[ne] -= price[ne]\n",
    "            return\n",
    "\n",
    "        ans = 0\n",
    "        d = collections.defaultdict(int)\n",
    "        for s,e in trips:\n",
    "            self.res = 1e9\n",
    "            vis = {s}\n",
    "            d[s]  += price[s]\n",
    "            dfs(s, e, vis)\n",
    "\n",
    "        def slove(s, f, ):\n",
    "            if not g[s]:\n",
    "                return d[s], d[s]//2\n",
    "\n",
    "            yes = d[s] // 2  #除2\n",
    "            no = d[s]\n",
    "            for e in g[s]:\n",
    "                if e != f:\n",
    "\n",
    "                    yy, nn = slove(e, s)\n",
    "                    yes += nn\n",
    "                    no += min(yy,nn)\n",
    "            return yes, no\n",
    "\n",
    "        yes, no = slove(0,-1 )\n",
    "        ans += min(yes, no)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "\n",
    "        g=defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        cnt=Counter()\n",
    "\n",
    "        def get(s,e):\n",
    "            def dfs(u,fa):\n",
    "                \n",
    "                if u==e:return True\n",
    "                for v in g[u]:\n",
    "                    if v==fa:continue\n",
    "                    if dfs(v,u):\n",
    "                        cnt[v]+=1\n",
    "                        return True\n",
    "                return False\n",
    "            \n",
    "            dfs(s,-1)\n",
    "    \n",
    "        for s,e in trips:\n",
    "            cnt[s]+=1\n",
    "            get(s,e)\n",
    "            # print(cnt)\n",
    "\n",
    "\n",
    "        def dfs(u,fa):\n",
    "            choose,no_choose=price[u]*cnt[u]//2,price[u]*cnt[u]\n",
    "            for v in g[u]:\n",
    "                if v==fa:continue\n",
    "                yes,no=dfs(v,u)\n",
    "                choose+=no\n",
    "                no_choose+=min(yes,no)\n",
    "            return choose,no_choose\n",
    "        \n",
    "        return min(dfs(0,-1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        cnt = [0] * n\n",
    "        def dfs(pa, cur, end):\n",
    "            if cur == end:\n",
    "                cnt[end] += 1 \n",
    "                return True\n",
    "            for nx in g[cur]:\n",
    "                if pa != nx:\n",
    "                    if dfs(cur, nx, end):\n",
    "                        cnt[cur] += 1\n",
    "                        return True\n",
    "            return False\n",
    "        for s, e in trips:\n",
    "            dfs(-1, s, e)\n",
    "\n",
    "        def search(pa, cur):\n",
    "            a = cnt[cur] * price[cur]\n",
    "            h = a // 2\n",
    "            for y in g[cur]:\n",
    "                if pa != y:\n",
    "                    a1, h1 = search(cur, y)\n",
    "                    a += min(a1,h1)\n",
    "                    h += a1 \n",
    "            return a, h\n",
    "        \n",
    "        # print(f'cnt={cnt}')\n",
    "        return min(search(-1, 0))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        qs = [[] for _ in range(n)]\n",
    "        for s, e in trips:\n",
    "            qs[s].append(e)  # 路径端点分组\n",
    "            if s != e:\n",
    "                qs[e].append(s)\n",
    "\n",
    "        # 并查集模板\n",
    "        pa = list(range(n))\n",
    "        def find(x: int) -> int:\n",
    "            if x != pa[x]:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "\n",
    "        diff = [0] * n\n",
    "        father = [0] * n\n",
    "        color = [0] * n\n",
    "        def tarjan(x: int, fa: int) -> None:\n",
    "            father[x] = fa\n",
    "            color[x] = 1  # 递归中\n",
    "            for y in g[x]:\n",
    "                if color[y] == 0:  # 未递归\n",
    "                    tarjan(y, x)\n",
    "                    pa[y] = x  # 相当于把 y 的子树节点全部 merge 到 x\n",
    "            for y in qs[x]:\n",
    "                # color[y] == 2 意味着 y 所在子树已经遍历完\n",
    "                # 也就意味着 y 已经 merge 到它和 x 的 lca 上了\n",
    "                if y == x or color[y] == 2:  # 从 y 向上到达 lca 然后拐弯向下到达 x\n",
    "                    diff[x] += 1\n",
    "                    diff[y] += 1\n",
    "                    lca = find(y)\n",
    "                    diff[lca] -= 1\n",
    "                    if father[lca] >= 0:\n",
    "                        diff[father[lca]] -= 1\n",
    "            color[x] = 2  # 递归结束\n",
    "        tarjan(0, -1)\n",
    "\n",
    "        def dfs(x: int, fa: int) -> (int, int, int):\n",
    "            not_halve, halve, cnt = 0, 0, diff[x]\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    nh, h, c = dfs(y, x)  # 计算 y 不变/减半的最小价值总和\n",
    "                    not_halve += min(nh, h)  # x 不变，那么 y 可以不变，可以减半，取这两种情况的最小值\n",
    "                    halve += nh  # x 减半，那么 y 只能不变\n",
    "                    cnt += c  # 自底向上累加差分值\n",
    "            not_halve += price[x] * cnt  # x 不变\n",
    "            halve += price[x] * cnt // 2  # x 减半\n",
    "            return not_halve, halve, cnt\n",
    "        return min(dfs(0, -1)[:2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in  range(n)]\n",
    "        for s,e in edges:\n",
    "            g[s].append(e)\n",
    "            g[e].append(s)\n",
    "        cnt = [0]*n \n",
    "        for start,end in trips:\n",
    "            def dfs(x,fa):\n",
    "                if x==end:\n",
    "                    cnt[x]+=1\n",
    "                    return True\n",
    "                for c in g[x]:\n",
    "                    if c!=fa and dfs(c,x):\n",
    "                        cnt[x]+=1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(start,-1)\n",
    "        # print(cnt)\n",
    "        def dfs(x,fa):\n",
    "            s1,s2 = [],[]\n",
    "            for c in g[x]:\n",
    "                if c==fa:\n",
    "                    continue\n",
    "                get,no_get = dfs(c,x)# 打折、不打折\n",
    "                s1.append(get)\n",
    "                s2.append(no_get)\n",
    "            have= price[x]//2*cnt[x]+sum(s2)\n",
    "            no_have = price[x]*cnt[x]+sum([min(a,b) for a,b in zip(s1,s2)])\n",
    "            print(x,have,no_have)\n",
    "            return have,no_have\n",
    "        return min(dfs(0,-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        nei = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            nei[a].append(b)\n",
    "            nei[b].append(a)\n",
    "        path = []\n",
    "        path_list = []    \n",
    "        def dfs(i:int,fa:int,target:int)->int:\n",
    "            if i == target:\n",
    "                path.append(target)\n",
    "                path_list.append(path.copy())\n",
    "                path.pop()\n",
    "            else:\n",
    "                for j in nei[i]:\n",
    "                    if j == fa:continue\n",
    "                    path.append(i)\n",
    "                    dfs(j,i,target)\n",
    "                    path.pop()\n",
    "        for s,e in trips:\n",
    "            dfs(s,-1,e)\n",
    "        cnt = {}\n",
    "        for p in path_list:\n",
    "            for node in p:\n",
    "                if node not in cnt:\n",
    "                    cnt[node] = 1\n",
    "                else:\n",
    "                    cnt[node]+=1\n",
    "        def dp(i:int,fa:int):\n",
    "            v,half_v = 0,0\n",
    "            if i in cnt:\n",
    "                v,half_v = price[i]*cnt[i],price[i]//2*cnt[i]\n",
    "            for j in nei[i]:\n",
    "                if j == fa:continue\n",
    "                tmp_v,tmp_v_half = dp(j,i)\n",
    "                half_v+=tmp_v\n",
    "                v+=min(tmp_v,tmp_v_half)\n",
    "            return v,half_v\n",
    "        return min(dp(0,-1))               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        # 1. 计算每个节点需要经过的次数\n",
    "        # 2， 树形dp，找出最小的cost\n",
    "\n",
    "        # 建树\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            tree[x].append(y)\n",
    "            tree[y].append(x)\n",
    "        print(tree)\n",
    "        # 1.找cnt\n",
    "        cnt = [0] * n\n",
    "        for start, end in trips:\n",
    "            # 找路径，找到终点x就返回true\n",
    "            @cache\n",
    "            def dfs(x: int, father: int) -> bool:\n",
    "                if x == end:\n",
    "                    cnt[x] += 1\n",
    "                    return True\n",
    "                for y in tree[x]:\n",
    "                    if y != father and dfs(y, x):\n",
    "                        cnt[x] += 1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(start, -1)\n",
    "        print(cnt)\n",
    "        \n",
    "        # 2.dp\n",
    "        # return (当前节点减半， 不减半)\n",
    "        def dfs(x: int, father:int) ->(int, int):\n",
    "            not_halve = price[x] * cnt[x]\n",
    "            halve = not_halve//2\n",
    "            for y in tree[x]:\n",
    "                if y != father:\n",
    "                    nh, h = dfs(y, x)\n",
    "                    not_halve += min(nh, h)\n",
    "                    halve += nh\n",
    "            return not_halve, halve\n",
    "        return min(dfs(0, -1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        #简单路径上的代价就是每次旅行所需要的花费\n",
    "        #先预处理出所有节点需要经过的次数,树上求lca\n",
    "\n",
    "        pa=[0]*n\n",
    "        x_len=[0]*n\n",
    "        def dfs(x:int,fa:int)->int:\n",
    "            for y in g[x]:\n",
    "                if y==fa:continue  \n",
    "                pa[y]=x\n",
    "                x_len[y]=x_len[x]+1\n",
    "                dfs(y,x)\n",
    "        dfs(0,-1)\n",
    "\n",
    "        cnt=[0]*n\n",
    "        def calc(x:int,y:int):\n",
    "            if x==y:\n",
    "                cnt[x]+=1\n",
    "                return\n",
    "            if x_len[x]>x_len[y]:\n",
    "                x,y=y,x\n",
    "            cnt[y]+=1\n",
    "            calc(x, pa[y])\n",
    "        \n",
    "        for s,e in trips:\n",
    "            calc(s, e)\n",
    "\n",
    "        #类似选或不选的思想\n",
    "        def dfs2(x:int,fa:int)->(int,int):\n",
    "            s1,s2=cnt[x]*price[x]//2,cnt[x]*price[x]   #1代表减半了，2代表没减半\n",
    "            for y in g[x]:\n",
    "                if y==fa:continue  \n",
    "                f1,f2=dfs2(y,x)\n",
    "                s1+=f2\n",
    "                s2+=min(f1,f2)\n",
    "            return s1,s2\n",
    "        \n",
    "        return min(dfs2(0,-1))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        # 1. 计算每个节点需要经过的次数\n",
    "        # 2， 树形dp，找出最小的cost\n",
    "\n",
    "        # 建树\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            tree[x].append(y)\n",
    "            tree[y].append(x)\n",
    "        print(tree)\n",
    "        # 1.找cnt\n",
    "        cnt = [0] * n\n",
    "        for start, end in trips:\n",
    "            # 找路径，找到终点x就返回true\n",
    "            @cache\n",
    "            def dfs(x: int, father: int) -> bool:\n",
    "                if x == end:\n",
    "                    cnt[x] += 1\n",
    "                    return True\n",
    "                for y in tree[x]:\n",
    "                    if y != father and dfs(y, x):\n",
    "                        cnt[x] += 1\n",
    "                        return True\n",
    "                return False\n",
    "            dfs(start, -1)\n",
    "        print(cnt)\n",
    "        \n",
    "        # 2.dp\n",
    "        # return (当前节点减半， 不减半)\n",
    "        def dfs(x: int, father:int) ->(int, int):\n",
    "            not_halve = price[x] * cnt[x]\n",
    "            halve = not_halve//2\n",
    "            for y in tree[x]:\n",
    "                if y != father:\n",
    "                    nh, h = dfs(y, x)\n",
    "                    not_halve += min(nh, h)\n",
    "                    halve += nh\n",
    "            return not_halve, halve\n",
    "        return min(dfs(0, -1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find(self, uf: List[int], i: int) -> int:\n",
    "        if uf[i] == i:\n",
    "            return i\n",
    "        uf[i] = self.find(uf, uf[i])\n",
    "        return uf[i]\n",
    "\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        next = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            next[edge[0]].append(edge[1])\n",
    "            next[edge[1]].append(edge[0])\n",
    "        \n",
    "        query = [[] for _ in range(n)]\n",
    "        for trip in trips:\n",
    "            query[trip[0]].append(trip[1])\n",
    "            if trip[0] != trip[1]:\n",
    "                query[trip[1]].append(trip[0])\n",
    "        \n",
    "        uf, visited, diff, parent = [0 for _ in range(n)], [False for _ in range(n)], [0 for _ in range(n)], [0 for _ in range(n)]\n",
    "        def tarjan(node: int, p: int):\n",
    "            parent[node], uf[node] = p, node\n",
    "            for child in next[node]:\n",
    "                if child == p:\n",
    "                    continue\n",
    "                tarjan(child, node)\n",
    "                uf[child] = node\n",
    "            for node1 in query[node]:\n",
    "                if node != node1 and not visited[node1]:\n",
    "                    continue\n",
    "                lca = self.find(uf, node1)\n",
    "                diff[node] += 1\n",
    "                diff[node1] += 1\n",
    "                diff[lca] -= 1\n",
    "                if parent[lca] >= 0:\n",
    "                    diff[parent[lca]] -= 1\n",
    "            visited[node] = True\n",
    "        tarjan(0, -1)\n",
    "\n",
    "        count = [0] * n\n",
    "        def dfs(node: int, p: int) -> int:\n",
    "            count[node] = diff[node]\n",
    "            for child in next[node]:\n",
    "                if child == p:\n",
    "                    continue\n",
    "                count[node] += dfs(child, node)\n",
    "            return count[node]\n",
    "        dfs(0, -1)\n",
    "\n",
    "        def dp(node: int, p: int) -> List[int]:\n",
    "            res = [\n",
    "                price[node] * count[node], price[node] * count[node] // 2\n",
    "            ]\n",
    "            for child in next[node]:\n",
    "                if child == p:\n",
    "                    continue\n",
    "                [x, y] = dp(child, node)\n",
    "                # node 没有减半，因此可以取子树的两种情况的最小值\n",
    "                # node 减半，只能取子树没有减半的情况\n",
    "                res[0], res[1] = res[0] + min(x, y), res[1] + x\n",
    "            return res\n",
    "\n",
    "        return min(dp(0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        ad=collections.defaultdict(list)\n",
    "\n",
    "        for s,e in edges:\n",
    "            ad[s].append(e)\n",
    "            ad[e].append(s)\n",
    "\n",
    "        cnt=[0]*n \n",
    "        for start,end in trips:\n",
    "            def dfs(cur,fa):\n",
    "                if cur==end:\n",
    "                    cnt[cur]+=1\n",
    "                    return True\n",
    "                for nex in ad[cur]:\n",
    "                    if nex!=fa and dfs(nex,cur):\n",
    "                        cnt[cur]+=1\n",
    "                        return True \n",
    "                return False\n",
    "            dfs(start,-1)\n",
    "       \n",
    "        def check(cur,fa):\n",
    "            nohalf=cnt[cur]*price[cur]\n",
    "            half=nohalf//2\n",
    "            for nex in ad[cur]:\n",
    "                if nex!=fa:\n",
    "                    nh,h=check(nex,cur)\n",
    "                    nohalf+=min(nh,h)\n",
    "                    half+=nh\n",
    "            return nohalf,half\n",
    "\n",
    "        \n",
    "        return min(check(0,-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        cost = [0] * n\n",
    "        def dfs(x, fa, target):\n",
    "            if x == target:\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    if dfs(y, x, target):\n",
    "                        cost[y] += price[y]\n",
    "                        return True\n",
    "            return False\n",
    "        for x, y in trips:\n",
    "            cost[x] += price[x]\n",
    "            dfs(x, -1, y)\n",
    "        print(cost)\n",
    "        def dp(x, fa):\n",
    "            if len(g[x]) == 1 and fa in g[x]:\n",
    "                return cost[x] // 2, cost[x]\n",
    "            cur_no_half = cost[x]\n",
    "            cur_half = cost[x] // 2\n",
    "            for y in g[x]:\n",
    "                if y == fa:\n",
    "                    continue\n",
    "                child_half, child_no_half = dp(y, x)\n",
    "                cur_no_half += min(child_half, child_no_half)\n",
    "                cur_half += child_no_half\n",
    "            return cur_half, cur_no_half\n",
    "        return min(dp(0, -1))\n",
    "\n",
    "                \n",
    "                \n",
    "                \n",
    "        return 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        cnt = [0] * n\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        def process(st, ed):\n",
    "            path = []\n",
    "            def dfs(u, fa):\n",
    "                path.append(u)\n",
    "                if u == ed:\n",
    "                    for i in path:\n",
    "                        cnt[i] += 1\n",
    "                else:\n",
    "                    for ne in g[u]:\n",
    "                        if ne != fa:\n",
    "                            dfs(ne, u)\n",
    "                path.pop()\n",
    "            dfs(st, -1)\n",
    "        for st, ed in trips:\n",
    "            process(st, ed)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(u, fa, half):\n",
    "            cost = cnt[u] * price[u]\n",
    "            if half: cost //= 2\n",
    "            ans = 0\n",
    "            for ne in g[u]:\n",
    "                if ne != fa:\n",
    "                    res = dfs(ne, u, False)\n",
    "                    if not half:\n",
    "                        res = min(res, dfs(ne, u, True))\n",
    "                    ans += res\n",
    "            return  cost + ans\n",
    "        return min(dfs(0, -1, True), dfs(0, -1, False))\n",
    "            \n",
    "        \n",
    "            \n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pa = [0] * 50\r\n",
    "path = [0] * 50 # visited nodes on path from node 0 to node i\r\n",
    "lca = [0] * 100 # lowest common ancestor of the two nodes in trips[i]\r\n",
    "conn = [0] * 50 # connected neighbors of node\r\n",
    "cnt = [0] * 50 # count of nodes in all trips\r\n",
    "vis = 0\r\n",
    "qry: list[dict[int, list[int]]] = [{} for _ in range(50)] # qry[i][j] is list of idx, where trips[idx] is between i, j\r\n",
    "\r\n",
    "def find(i: int) -> int:\r\n",
    "    if pa[i] != i: pa[i] = find(pa[i])\r\n",
    "    return pa[i]\r\n",
    "\r\n",
    "def tarjan(u: int) -> None:\r\n",
    "    global vis\r\n",
    "    vis |= 1 << u\r\n",
    "    pa[u] = u\r\n",
    "    ngh = conn[u] & (conn[u] ^ vis)\r\n",
    "    v = 0\r\n",
    "\r\n",
    "    while ngh:\r\n",
    "        if ngh & 1:\r\n",
    "            path[v] = path[u] | (1 << u)\r\n",
    "            tarjan(v)\r\n",
    "            pa[v] = u\r\n",
    "        v += 1\r\n",
    "        ngh >>= 1\r\n",
    "\r\n",
    "    for v, indices in qry[u].items():\r\n",
    "        if ((vis >> v) & 1) == 0: continue\r\n",
    "        w = find(v)\r\n",
    "        for i in indices:\r\n",
    "            lca[i] = w\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\r\n",
    "        global vis\r\n",
    "        # initialize global variables\r\n",
    "        for i in range(n):\r\n",
    "            pa[i] = i\r\n",
    "            path[i] = 0\r\n",
    "            conn[i] = 0\r\n",
    "            cnt[i] = 0\r\n",
    "            qry[i].clear()\r\n",
    "        for i, (u, v) in enumerate(trips):\r\n",
    "            qry[u].setdefault(v, list())\r\n",
    "            qry[v].setdefault(u, list())\r\n",
    "            qry[u][v].append(i)\r\n",
    "            qry[v][u].append(i)\r\n",
    "        for u, v in edges:\r\n",
    "            conn[u] |= 1 << v\r\n",
    "            conn[v] |= 1 << u\r\n",
    "        \r\n",
    "        vis = 0\r\n",
    "        tarjan(0)\r\n",
    "        # path from root 0 to all nodes, and lca of all trips are obtained from tarjan postorder dfs\r\n",
    "        # sum up total count of appearance of each vertex in all trips\r\n",
    "        for i, (u, v) in enumerate(trips):\r\n",
    "        # route is all nodes from root to u, from root to v, but not root to lca\r\n",
    "            rte = (path[u] | path[v]) ^ path[lca[i]]\r\n",
    "            if rte >> u & 1 == 0:\r\n",
    "                cnt[u] += 1\r\n",
    "            if u != v and rte >> v & 1 == 0:\r\n",
    "                cnt[v] += 1\r\n",
    "            w = 0\r\n",
    "            while rte:\r\n",
    "                if rte & 1:\r\n",
    "                    cnt[w] += 1\r\n",
    "                rte >>= 1\r\n",
    "                w += 1\r\n",
    "        \r\n",
    "        # maximum reduction in cost, discount on node, and not discount on node\r\n",
    "        def disc(u: int) -> tuple[int, int]:\r\n",
    "            global vis\r\n",
    "            vis |= 1 << u\r\n",
    "            wt = cnt[u] * price[u] // 2\r\n",
    "            wo = 0\r\n",
    "            child = conn[u] & (conn[u] ^ vis)\r\n",
    "            v = 0\r\n",
    "            while child:\r\n",
    "                if child & 1:\r\n",
    "                    cwt, cwo = disc(v)\r\n",
    "                    wt += cwo\r\n",
    "                    wo += max(cwt, cwo)\r\n",
    "                child >>= 1\r\n",
    "                v += 1\r\n",
    "            return wt, wo\r\n",
    "        \r\n",
    "        vis = 0\r\n",
    "        return sum(c * p for c, p in zip(cnt, price)) - max(disc(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        cnt = [0] * n\n",
    "        def dfs(st, fa, ed, cur):\n",
    "            cur.append(st)\n",
    "            if st == ed:\n",
    "                for i in cur:\n",
    "                    cnt[i] += 1\n",
    "                return\n",
    "            for ne in g[st]:\n",
    "                if ne == fa:\n",
    "                    continue\n",
    "                dfs(ne, st, ed, cur)\n",
    "            cur.pop()\n",
    "        for st, ed in trips:\n",
    "            dfs(st, -1, ed, [])\n",
    "        @cache\n",
    "        def dfs(u, fa, last):\n",
    "            cur = price[u] * cnt[u]\n",
    "            ans = inf\n",
    "            if not last:\n",
    "                res = cur // 2\n",
    "                for ne in g[u]:\n",
    "                    if ne == fa:\n",
    "                        continue\n",
    "                    res += dfs(ne, u, True)\n",
    "                ans = res\n",
    "            res = cur\n",
    "            for ne in g[u]:\n",
    "                if ne == fa:\n",
    "                    continue\n",
    "                res += min(dfs(ne, u, True), dfs(ne, u, False))\n",
    "            return min(ans, res)\n",
    "        return dfs(0, -1, False)\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        d = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            d[i].append(j)\n",
    "            d[j].append(i)\n",
    "        tree = JumpOnTree(d)\n",
    "        val = [0] * n\n",
    "        for i, j in trips:\n",
    "            while i != j:\n",
    "                val[i] += 1\n",
    "                i = tree.jump(i, j, 1)\n",
    "            val[i] += 1\n",
    "        dp = [[0] * 2 for _ in range(n)]\n",
    "        def dfs(i, fa):\n",
    "            dp[i][0] = price[i] * val[i]\n",
    "            dp[i][1] = price[i] // 2 * val[i]\n",
    "            for j in d[i]:\n",
    "                if j == fa:\n",
    "                    continue\n",
    "                dfs(j, i)\n",
    "                dp[i][1] += dp[j][0]\n",
    "                dp[i][0] += min(dp[j])\n",
    "        dfs(0, -1)\n",
    "        return min(dp[0])\n",
    "            \n",
    "            \n",
    "            \n",
    "class JumpOnTree:\n",
    "    def __init__(self, edges, root=0):\n",
    "        self.n = len(edges)\n",
    "        self.edges = edges\n",
    "        self.root = root\n",
    "        self.logn = (self.n - 1).bit_length()\n",
    "        self.depth = [-1] * self.n\n",
    "        self.depth[self.root] = 0\n",
    "        self.parent = [[-1] * self.n for _ in range(self.logn)]\n",
    "        self.dfs()\n",
    "        self.doubling()\n",
    " \n",
    "    def dfs(self):\n",
    "        stack = [self.root]\n",
    "        while stack:\n",
    "            u = stack.pop()\n",
    "            for v in self.edges[u]:\n",
    "                if self.depth[v] == -1:\n",
    "                    self.depth[v] = self.depth[u] + 1\n",
    "                    self.parent[0][v] = u\n",
    "                    stack.append(v)\n",
    " \n",
    "    def doubling(self):\n",
    "        for i in range(1, self.logn):\n",
    "            for u in range(self.n):\n",
    "                p = self.parent[i - 1][u]\n",
    "                if p != -1:\n",
    "                    self.parent[i][u] = self.parent[i - 1][p]\n",
    " \n",
    "    def lca(self, u, v):\n",
    "        du = self.depth[u]\n",
    "        dv = self.depth[v]\n",
    "        if du > dv:\n",
    "            du, dv = dv, du\n",
    "            u, v = v, u\n",
    " \n",
    "        d = dv - du\n",
    "        i = 0\n",
    "        while d > 0:\n",
    "            if d & 1:\n",
    "                v = self.parent[i][v]\n",
    "            d >>= 1\n",
    "            i += 1\n",
    "        if u == v:\n",
    "            return u\n",
    " \n",
    "        logn = (du - 1).bit_length()\n",
    "        for i in range(logn - 1, -1, -1):\n",
    "            pu = self.parent[i][u]\n",
    "            pv = self.parent[i][v]\n",
    "            if pu != pv:\n",
    "                u = pu\n",
    "                v = pv\n",
    "        return self.parent[0][u]\n",
    " \n",
    "    def jump(self, u, v, k):\n",
    "        if k == 0:\n",
    "            return u\n",
    "        p = self.lca(u, v)\n",
    "        d1 = self.depth[u] - self.depth[p]\n",
    "        d2 = self.depth[v] - self.depth[p]\n",
    "        if d1 + d2 < k:\n",
    "            return -1\n",
    "        if k <= d1:\n",
    "            d = k\n",
    "        else:\n",
    "            u = v\n",
    "            d = d1 + d2 - k\n",
    "        i = 0\n",
    "        while d > 0:\n",
    "            if d & 1:\n",
    "                u = self.parent[i][u]\n",
    "            d >>= 1\n",
    "            i += 1\n",
    "        return u\n",
    " \n",
    "    def dist(self, u, v):\n",
    "        return self.depth[u] + self.depth[v] - 2 * self.depth[self.lca(u, v)]\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, e: List[List[int]], p: List[int], t: List[List[int]]) -> int:\n",
    "        g=[[] for i in range(n)]\n",
    "        for i,j in e:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "        def dfs(u,fa,f):\n",
    "            f[u]=fa\n",
    "            for i in g[u]:\n",
    "                if i!=fa:\n",
    "                    dfs(i,u,f)\n",
    "        h=[0]*n\n",
    "        for i,j in t:\n",
    "            f=[-1]*n\n",
    "            dfs(i,-1,f)\n",
    "            while j!=-1:\n",
    "                h[j]+=1\n",
    "                j=f[j]\n",
    "        @cache\n",
    "        def func(u,fa,flag):\n",
    "            a,b=p[u]*h[u]//2,p[u]*h[u]\n",
    "            for i in g[u]:\n",
    "                if i!=fa:\n",
    "                    b+=func(i,u,True)\n",
    "                    a+=func(i,u,False)\n",
    "            return min(a,b) if flag else b\n",
    "        return func(0,-1,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        # 非相邻节点价格减半，二分图，树上dp\n",
    "        g = defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        cnt = [0]*n #记录每个节点经过的次数\n",
    "        def dfs1(x,end,famer):\n",
    "            if x == end :\n",
    "                cnt[x] += 1\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != famer and dfs1(y,end,x):\n",
    "                    cnt[x] += 1\n",
    "                    # far为x的前一个节点，防止走回路\n",
    "                    return True\n",
    "            return False\n",
    "        for start,end in trips:\n",
    "            dfs1(start,end,-1)\n",
    "        print(cnt)\n",
    "\n",
    "        #类似打家劫舍\n",
    "        def dfs2(x,famer):\n",
    "            not_half = price[x]*cnt[x]\n",
    "            half = not_half//2\n",
    "            for y in g[x]:\n",
    "                if y != famer:\n",
    "                    nh,h = dfs2(y,x)\n",
    "                    not_half += min(nh,h)  # x不变，那么 y 可以不变，也可以减半，取这两种情况的最小值\n",
    "                    half += nh # x 减半，那么 y 只能不变\n",
    "            return not_half,half\n",
    "        return min(dfs2(0,-1))\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        def dfs(node,parent,end):\n",
    "            if node == end:\n",
    "                cnts[node] += 1\n",
    "                return True\n",
    "            for nxt in graph[node]:\n",
    "                if nxt != parent:\n",
    "                    if dfs(nxt,node,end):\n",
    "                        cnts[node] += 1\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        for u , v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        cnts = [0] * n\n",
    "\n",
    "        for u , v in trips:\n",
    "            dfs(u,None,v)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(node,parent,label):\n",
    "            no_ans = price[node] * cnts[node]\n",
    "            ans = (price[node]//2) * cnts[node]\n",
    "            for nxt in graph[node]:\n",
    "                if nxt != parent:\n",
    "                    no_ans += dfs(nxt,node,False)\n",
    "                    ans += dfs(nxt,node,True)\n",
    "            if label:return no_ans\n",
    "            return min(no_ans,ans)\n",
    "\n",
    "        return dfs(0,-1,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "\n",
    "        g=defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        def get(u,fa,e):\n",
    "            if u==e:return True\n",
    "            for v in g[u]:\n",
    "                if v==fa:continue\n",
    "                if get(v,u,e):\n",
    "                    cnt[v]+=1\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        \n",
    "        cnt=Counter()\n",
    "        for s,e in trips:\n",
    "            cnt[s]+=1\n",
    "            get(s,-1,e)\n",
    "      \n",
    "        \n",
    "        print(cnt)\n",
    "\n",
    "        def dfs2(u,fa):\n",
    "\n",
    "            choose=cnt[u]*price[u]//2\n",
    "            nochoose=cnt[u]*price[u]\n",
    "\n",
    "            for v in g[u]:\n",
    "                if v==fa:continue\n",
    "                yes,no=dfs2(v,u)\n",
    "                choose+=no\n",
    "                nochoose+=min(yes,no)\n",
    "            return choose,nochoose\n",
    "        \n",
    "        a,b=dfs2(0,-1)\n",
    "        return min(a,b)\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            u, v = edge\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        ctr = Counter()\n",
    "        \n",
    "        def dfs(x, y):\n",
    "            if x in vis: return False\n",
    "            if x == y: return True\n",
    "            \n",
    "            vis.add(x)\n",
    "            for nxt in graph[x]:\n",
    "                if dfs(nxt, y):\n",
    "                    ctr[nxt] += 1\n",
    "                    return True\n",
    "        \n",
    "        for x, y in trips:\n",
    "            vis = set()\n",
    "            ctr[x] += 1\n",
    "            dfs(x, y)\n",
    "        \n",
    "        \n",
    "        tree = {}\n",
    "        def dfs(node):\n",
    "            tree[node] = [\n",
    "                nxt\n",
    "                for nxt in graph[node]\n",
    "                if nxt not in tree\n",
    "            ]\n",
    "            for nxt in tree[node]:\n",
    "                dfs(nxt)\n",
    "        \n",
    "        dfs(0)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(node, half):\n",
    "            res = price[node] * ctr[node]\n",
    "            if half:\n",
    "                res //= 2\n",
    "            for nxt in tree[node]:\n",
    "                tmp = dfs(nxt, False)\n",
    "                if not half:\n",
    "                    tmp = min(tmp, dfs(nxt, True))\n",
    "                res += tmp\n",
    "\n",
    "            return res\n",
    "    \n",
    "        return min(dfs(0, True), dfs(0, False))\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\r\n",
    "        g = [[] for _ in range(n)]\r\n",
    "        for x, y in edges:\r\n",
    "            g[x].append(y)\r\n",
    "            g[y].append(x)  # 建树\r\n",
    "\r\n",
    "        qs = [[] for _ in range(n)]\r\n",
    "        for s, e in trips:\r\n",
    "            qs[s].append(e)  # 路径端点分组\r\n",
    "            if s != e:\r\n",
    "                qs[e].append(s)\r\n",
    "\r\n",
    "        # 并查集模板\r\n",
    "        pa = list(range(n))\r\n",
    "        def find(x: int) -> int:\r\n",
    "            if x != pa[x]:\r\n",
    "                pa[x] = find(pa[x])\r\n",
    "            return pa[x]\r\n",
    "\r\n",
    "        diff = [0] * n\r\n",
    "        father = [0] * n\r\n",
    "        color = [0] * n\r\n",
    "        def tarjan(x: int, fa: int) -> None:\r\n",
    "            father[x] = fa\r\n",
    "            color[x] = 1  # 递归中\r\n",
    "            for y in g[x]:\r\n",
    "                if color[y] == 0:  # 未递归\r\n",
    "                    tarjan(y, x)\r\n",
    "                    pa[y] = x  # 相当于把 y 的子树节点全部 merge 到 x\r\n",
    "            for y in qs[x]:\r\n",
    "                # color[y] == 2 意味着 y 所在子树已经遍历完\r\n",
    "                # 也就意味着 y 已经 merge 到它和 x 的 lca 上了\r\n",
    "                if y == x or color[y] == 2:  # 从 y 向上到达 lca 然后拐弯向下到达 x\r\n",
    "                    diff[x] += 1\r\n",
    "                    diff[y] += 1\r\n",
    "                    lca = find(y)\r\n",
    "                    diff[lca] -= 1\r\n",
    "                    if father[lca] >= 0:\r\n",
    "                        diff[father[lca]] -= 1\r\n",
    "            color[x] = 2  # 递归结束\r\n",
    "        tarjan(0, -1)\r\n",
    "\r\n",
    "        def dfs(x: int, fa: int) -> (int, int, int):\r\n",
    "            not_halve, halve, cnt = 0, 0, diff[x]\r\n",
    "            for y in g[x]:\r\n",
    "                if y != fa:\r\n",
    "                    nh, h, c = dfs(y, x)  # 计算 y 不变/减半的最小价值总和\r\n",
    "                    not_halve += min(nh, h)  # x 不变，那么 y 可以不变，可以减半，取这两种情况的最小值\r\n",
    "                    halve += nh  # x 减半，那么 y 只能不变\r\n",
    "                    cnt += c  # 自底向上累加差分值\r\n",
    "            not_halve += price[x] * cnt  # x 不变\r\n",
    "            halve += price[x] * cnt // 2  # x 减半\r\n",
    "            return not_halve, halve, cnt\r\n",
    "        return min(dfs(0, -1)[:2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        #tarjan算法求出lca，再使用差分树和差分DP\n",
    "\n",
    "        node=[[] for i in range(n)]\n",
    "        for edge in edges:\n",
    "            node[edge[0]].append(edge[1])\n",
    "            node[edge[1]].append(edge[0])\n",
    "        \n",
    "        query=[[] for i in range(n)]\n",
    "        #划分查询，查询需要拆成对半的\n",
    "        for trip in trips:\n",
    "            query[trip[0]].append(trip[1])\n",
    "            if trip[0]!=trip[1]:\n",
    "                query[trip[1]].append(trip[0])\n",
    "\n",
    "        #并查集\n",
    "        p=[i for i in range(n)]\n",
    "        def find(x):\n",
    "            if p[x]!=x:\n",
    "                p[x]=find(p[x])\n",
    "            return p[x]\n",
    "        \n",
    "        #记录一下每个节点的father，这里主要是差分树会用上\n",
    "        father=[-1 for i in range(n)]\n",
    "        vis_node=[0 for i in range(n)]  #标记某个节点是否已经被访问过了\n",
    "        sub_tree=[0 for i in range(n)]                                #差分树\n",
    "\n",
    "        def tarjan(cur,fa):\n",
    "            vis_node[cur]=1\n",
    "            father[cur]=fa\n",
    "\n",
    "            for i in node[cur]:\n",
    "                if not vis_node[i]:\n",
    "                    tarjan(i,cur)\n",
    "                    #子树遍历完成合并到当前树\n",
    "                    p[i]=cur\n",
    "            \n",
    "            for i in query[cur]:\n",
    "                if cur==i:\n",
    "                    sub_tree[cur]+=1\n",
    "                    if father[cur]!=-1:\n",
    "                        sub_tree[father[cur]]-=1\n",
    "                elif vis_node[i]==2:\n",
    "                    sub_tree[cur]+=1\n",
    "                    sub_tree[i]+=1\n",
    "                    lca=find(i)\n",
    "                    sub_tree[lca]-=1\n",
    "                    if father[lca]!=-1:\n",
    "                        sub_tree[father[lca]]-=1\n",
    "            vis_node[cur]=2\n",
    "            \n",
    "        tarjan(0,-1)\n",
    "\n",
    "        value=[[0,0] for i in range(n)]\n",
    "        def dfs(cur,fa):\n",
    "            for i in node[cur]:\n",
    "                if i!=fa:\n",
    "                    dfs(i,cur)\n",
    "                    sub_tree[cur]+=sub_tree[i]\n",
    "                    value[cur][0]+=min(value[i][0],value[i][1])\n",
    "                    value[cur][1]+=value[i][0]\n",
    "            value[cur][0]+=sub_tree[cur]*price[cur]\n",
    "            value[cur][1]+=sub_tree[cur]*price[cur]*0.5\n",
    "        \n",
    "        dfs(0,-1)\n",
    "        return int(min(value[0]))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        in_set = [0] * n\n",
    "\n",
    "        def findPath(x, y):\n",
    "            seen = [False] * n\n",
    "            def dfs1(x):\n",
    "                seen[x] = True\n",
    "                if x == y:\n",
    "                    return True\n",
    "                for u in g[x]:\n",
    "                    if not seen[u] and dfs1(u):\n",
    "                        in_set[u] += 1\n",
    "                        return True \n",
    "                return False\n",
    "\n",
    "            dfs1(x)\n",
    "            in_set[x] += 1\n",
    "        \n",
    "        for u, v in trips:\n",
    "            findPath(u, v)\n",
    "\n",
    "        def dfs(x):\n",
    "            seen[x] = True\n",
    "            if x is None:\n",
    "                return 0, 0\n",
    "            half = price[x]/2\n",
    "            n_half = price[x]\n",
    "\n",
    "            h_total, n_total = 0, 0\n",
    "            for y in g[x]:\n",
    "                if not seen[y]:\n",
    "                    p1, p2 = dfs(y)\n",
    "                    h_total += p2\n",
    "                    n_total += min(p1, p2)\n",
    "            \n",
    "            return half * in_set[x] + h_total, n_half * in_set[x] + n_total\n",
    "\n",
    "        seen = [False] * n\n",
    "        p1, p2 = dfs(0)\n",
    "        \n",
    "        return int(min(p1, p2))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\r\n",
    "\r\n",
    "        neighbor=[[] for i in range(n)]\r\n",
    "        for i in range(len(edges)):\r\n",
    "            neighbor[edges[i][0]].append(edges[i][1])\r\n",
    "            neighbor[edges[i][1]].append(edges[i][0])\r\n",
    "\r\n",
    "        target=[[] for i in range(n)]\r\n",
    "        for i in range(len(trips)):\r\n",
    "            x,y=trips[i]\r\n",
    "            if x==y:\r\n",
    "                target[x].append(x)\r\n",
    "            else:\r\n",
    "                target[x].append(y)\r\n",
    "                target[y].append(x)\r\n",
    "        \r\n",
    "        dsu=[i for i in range(n)]\r\n",
    "        def find(k:int):\r\n",
    "            if dsu[k]==k:\r\n",
    "                return k\r\n",
    "            else:\r\n",
    "                return find(dsu[k])\r\n",
    "            \r\n",
    "        dif=[0]*n\r\n",
    "        state=[0]*n\r\n",
    "        father=[0]*n\r\n",
    "        def updatedif(node:int,fa:int):\r\n",
    "            father[node]=fa\r\n",
    "            state[node]=1\r\n",
    "            for y in neighbor[node]:\r\n",
    "                if state[y]==0:\r\n",
    "                    updatedif(y,node)\r\n",
    "                    dsu[y]=node\r\n",
    "            for y in target[node]:\r\n",
    "                if y==node or state[y]==2:\r\n",
    "                    lcp=find(y)\r\n",
    "                    dif[node]+=1\r\n",
    "                    dif[y]+=1\r\n",
    "                    dif[lcp]-=1\r\n",
    "                    if father[lcp]!=-1:\r\n",
    "                        dif[father[lcp]]-=1\r\n",
    "            state[node]=2\r\n",
    "        updatedif(0,-1)\r\n",
    "\r\n",
    "        def solve(x:int,fa:int):\r\n",
    "            notselect,select,count=0,0,dif[x]\r\n",
    "            for y in neighbor[x]:\r\n",
    "                if y!=fa:\r\n",
    "                    ns,s,cnt=solve(y,x)\r\n",
    "                    notselect+=min(ns,s)\r\n",
    "                    select+=ns\r\n",
    "                    count+=cnt\r\n",
    "            notselect+=price[x]*count\r\n",
    "            select+=price[x]*count//2\r\n",
    "            return notselect,select,count\r\n",
    "        return min(solve(0,-1)[0:2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        pairs = [defaultdict(int) for _ in range(n)]\n",
    "        for a, b in trips:\n",
    "            pairs[a][b] += 1\n",
    "            if a != b:\n",
    "                pairs[b][a] += 1\n",
    "\n",
    "        parent = [None] * n\n",
    "        value = [None] * n\n",
    "        rank = [1] * n\n",
    "\n",
    "        def top(k):\n",
    "            if parent[k] is None:\n",
    "                return k\n",
    "            else:\n",
    "                t = top(parent[k])\n",
    "                parent[k] = t\n",
    "                return t\n",
    "\n",
    "        def merge(m, n):\n",
    "            t1 = top(m)\n",
    "            t2 = top(n)\n",
    "            if t1 != t2:\n",
    "                if rank[t1] < rank[t2]:\n",
    "                    t1, t2 = t2, t1\n",
    "                    value[t1] = value[t2]\n",
    "                parent[t2] = t1\n",
    "                rank[t1] += rank[t2]\n",
    "\n",
    "        anc = [0] * n\n",
    "\n",
    "        def dfs1(x, p):\n",
    "            value[x] = x\n",
    "            for b, c in pairs[x].items():\n",
    "                t = top(b)\n",
    "                if value[t] is not None:\n",
    "                    anc[value[t]] += c\n",
    "            for b in graph[x]:\n",
    "                if b != p:\n",
    "                    dfs1(b, x)\n",
    "                    merge(x, b)\n",
    "\n",
    "        dfs1(0, None)\n",
    "        \n",
    "        multiplier = [0] * n\n",
    "\n",
    "        def dfs2(x, p):\n",
    "            r = 0\n",
    "            for b, c in pairs[x].items():\n",
    "                r += c\n",
    "                if b == x:\n",
    "                    r += c\n",
    "            for b in graph[x]:\n",
    "                if b != p:\n",
    "                    r += dfs2(b, x)\n",
    "            r -= anc[x]\n",
    "            multiplier[x] = r\n",
    "            return r - anc[x]\n",
    "        dfs2(0, None)\n",
    "\n",
    "        @cache\n",
    "        def dfs3(x, p, can_half):\n",
    "            # no half\n",
    "            ans = price[x] * multiplier[x]\n",
    "            for b in graph[x]:\n",
    "                if b != p:\n",
    "                    ans += dfs3(b, x, True)\n",
    "            if can_half:\n",
    "                ans2 = price[x] // 2 * multiplier[x]\n",
    "                for b in graph[x]:\n",
    "                    if b != p:\n",
    "                        ans2 += dfs3(b, x, False)\n",
    "                ans = min(ans, ans2)\n",
    "            return ans\n",
    "\n",
    "        return dfs3(0, None, True)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
